Session 1

Discrete Optimizations

(Chair:

Weili Wu)

13:00 - 13:15

Matthieu Latapy, Thi Ha Duong Phan, Christophe Crespelle*, and Thanh Qui Nguyen, Termination of Multipartite Graph Series Arising from Complex Network Modelling.

13:15 - 13:30

Andreas Emil Feldmann*, Shantanu Das, and Peter Widmayer, Simpler Cuts are Fast and Good: Optimum Right-Angled Cuts in Solid Grids.

13:30 - 13:45

Sándor Fekete, Chris Gray, and Alexander Kroeller*, Evacuation of Rectilinear Polygons.

13:45 - 14:00

Ararat Harutyunyan*, Fast Algorithms for Alliances in Trees.

14:00 - 14:15

Jun Luo, Ovidiu Daescu*, and Wenqi Ju, NP-Completeness of Spreading Colored Points.

14:15 - 14:30

Loreto Gonzalez-Hernandez*, Nelson Rangel-Valdez, and Jose Torres-Jimenez, Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach.

Coffee Break

14:30 - 14:45

Session 2

Discrete Optimization

(Chair: Ovidiu Daescu)

14:45- 15:00

Pietro Belotti, Sonia Cafieri, Jon Lee, and Leo Liberti*, Feasibility-Based Bounds Tightening via Fixed Points.

15:00 - 15:15

Takashi Matsuhisa*, A Characterisation of Stable Sets in Game with Transitive Preference.

15:15 - 15:30

Yi Shi*, Maryam Hasan, Zhipeng Cai, Guohui Lin, and Dale Schuurmans, Linear Coherent Bi-Cluster Discovery via Beam Detection and Sample Set Clustering.

15:30 - 15:45

Bingbing Zhuang and Hiroshi Nagamochi*, Listing Triconnected Rooted Plane Graphs.

15:45 - 16:00

Mingyu Xiao*, Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs.

16:00 - 16:15

David Eppstein, Michael T. Goodrich, Darren Strash, and Lowell Trott*, Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures.

16:15 - 16:30

Yakov Zinder, Julia Memar*, and Gaurav Singh, Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets.

Session 3

Optimization in Graphs

(Chair: Zhao Zhang)

8:30 - 8:45

Giuseppe F. Italiano, Luigi Laura*, and Federico Santaroni, Finding Strong Bridges and Strong Articulation Points in Linear Time.

8:45 - 9:00

Neng Fan* and Panos M. Pardalos, Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks.

9:00 - 9:15

Vamsi Kundeti, Sanguthevar Rajasekaran*, and Heiu Dinh, An Efficient Algorithm For Chinese Postman Walk on Bi-Directed de Bruijn Graphs.

9:15 - 9:30

James Nastos* and Yong Gao, A Novel Branching Strategy for Parameterized Graph Modification Problems.

9:30 - 9:45

Zhihua Yu, Qinghai Liu, and Zhao Zhang*, Cyclic Vertex Connectivity of Star Graphs.

9:45 - 10:00

Eddie Cheng, Ke Qiu*, and Zhi Zhang Shen, The Number of Shortest Paths in The (n, k)-Star Graphs.

10:00 - 10:15

Cristina Bazgan, Sonia Toubaline*, and Daniel Vanderpooten, Complexity of Determining The Most Vital Elements for The 1-Median and 1-Center Location Problems.

Coffee Break

10:15 - 10:30

Session 4

Approximations  

(Chair: Xiaodong Hu)

10:30 - 10:45

Hongwei Du*, Qiang Ye, Jiaofei Zhong, Amy Wang, Wonjun Lee, and Haesun Park, PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks.

10:45 - 11:00

Viet Hung Nguyen*, A Primal-Dual Approximation Algorithm for The Asymmetric Prize-Collecting TSP.

11:00 - 11:15

Danny Z. Chen and Ewa Misiolek*, Computing Toolpaths for 5-Axis NC Machines.

11:15 - 11:30

Tomoyuki Yamakami*, A Trichotomy Theorem for The Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs.

11:30 - 11:45

Jin-Yi Liu*, Randomized Algorithms for Weighted Approximation of Points by a Step Function.

11:45 - 12:00

Zhixiang Chen and Bin Fu*, Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials.

Lunch Time

12:00 - 13:00

Session 5

Geometric Optimization and Scheduling

(Chair: Marina Gavrilova)

13:00 - 13:15

André Schulz and Csaba Toth*, The Union of Colorful Simplices Spanned by A Colored Point Set.

13:15 - 13:30

Xin He, Jiun-Jie Wang, and Huaming Zhang*, Compact Visibility Representation of 4-Connected Plane Graphs.

13:30 - 13:45

Arindam Karmakar, Sandip Das*, Subhas C. Nandy, and Binay Bhattacharya, Some Variations on Constrained Minimum Enclosing Circle Problem.

13:45 - 14:00

Elmar Langetepe*, Searching for An Axis-Parallel Shoreline.

14:00 - 14:15

Evangelos Kranakis, Danny Krizanc, Oscar Morales*, and Ladislav Stacho, Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs.

14:15 - 14:30

Fei Li*, Scheduling Packets with Values and Deadlines in Size-Bounded Buffers.

14:30 - 14:45

Hans Kellerer, Alan J. Soper, and Vitaly A. Strusevich*, Transporting Jobs Through a Processing Center with Two Parallel Machines.

Coffee Break

14:45 - 15:00

Session 6

Network Optimization

(Chair: Huaming Zhang)

15:00 - 15:15

Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian*, Erik D. Demaine, Vida Dujmovic, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristan, Diane Souvaine, and Ryuhei Uehara, Coverage with k-Transmitters in The Presence of Obstacles.

15:15 - 15:30

Beate Bollig*, On Symbolic OBDD-Based Algorithms for The Minimum Spanning Tree Problem.

15:30 - 15:45

Xujin Chen*, Xiaodong Hu, and Weidong Ma, Reducing The Maximum Latency of Selfish Ring Routing via Pairwise Cooperations.

15:45 - 16:00

Marjan Marzban, Qianping Gu*, and Xiaohua Jia, Computational Study for Planar Connected Dominating Set Problem.

16:00 - 16:15

Balasingham Balamohan, Paola Flocchini*, Ali Miri, and Nicola Santoro, Time Optimal Algorithms for Black Hole Search in Rings.

16:15 - 16:30

Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Jaroslav Opatrny, Oscar Morales*, and Ladislav Stacho, Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle.

Session 7

Approximations  

(Chair: Donghyun Kim)

8:30 - 8:45

Martin Olsen, Anastasios Viglas, and Ilia Zvedeniouk*, A Constant Approximation Algorithm for the Link Building Problem.

8:45 - 9:00

Artem Chebotko and Bin Fu*, XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme.

9:00 - 9:15

Masashi Kiyomi, Toshiki Saitoh*, and Ryuhei Uehara, Bipartite Permutation Graphs are Reconstructible.

9:15 - 9:30

Peter Damaschke* and Azam Sheikh Muhammad, Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives.

9:30 - 9:45

Tomoshi Otsuki*, Hideyuki Aisu, and Toshiaki Tanaka, A Search-Based Approach to The Railway Rolling Stock Allocation Problem.

9:45 - 10:00

Viet Hung Nguyen*, Approximation Algorithm for The Minimum Directed Tree Cover.

10:00 - 10:15

Jing He and Hongyu Liang*, An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs.

Coffee Break

10:15 - 10:30

Session 8

 Optimization in Graphs 

(Chair: Viet Hung Nguyen)

10:30 - 10:45

Guizhen Liu, Xuejun Pan, and Jonathan Z. Sun*, A New Result on [k,k+1]-Factors Containing Given Hamiltonian Cycles.

10:45 - 11:00

Mirela Damian* and Kristin Raudonis, Yao Graphs Span Theta Graphs.

11:00 - 11:15

Tadao Takaoka* and Mashitoh Hashim, A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n^2log n) Expected Time.

11:15 - 11:30

Arthur H. Busch*, Feodor E. Dragan, and R. Sritharan, New Min-Max Theorems for Weakly Chordal Graphs and Dually Chordal Graphs, and a New Class of Hypergraphs.

11:30 - 11:45

Bang Ye Wu*, A Simpler and More Efficient Algorithm for The Next-To-Shortest Path Problem.

11:45 - 12:00

Boting Yang*, Fast Edge-Searching and Related Problems.

Lunch Time

12:00 - 13:00

Session 9

Network Optimization

(Chair: Boting Yang)

13:00 - 13:15

Wei Ding*, Guohui Lin, and Guoliang Xue, Diameter-Constrained Steiner Tree.

13:15 - 13:30

Gianlorenzo D'Angelo*, Gabriele Di Stefano, and Alfredo Navarra, Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks.

13:30 - 13:45

Wei Ding* and Guoliang Xue, A Divide-and-Conquer Algorithm for Computing A Most Reliable Source on An Unreliable Ring-Embedded Tree.

13:45 - 14:00

Asish Mukhopadhyay*, Animesh Sarker, and Tom Switzer, Approximate ellipsoid in the streaming model.

14:00 - 14:15

Hongbing Fan* and Yu-Liang Wu, Structural Overlay Network for File Distribution.

14:15 - 14:30

Evangelos Kranakis*, Danny Krizanc, Ioannis Lambadaris, Lata Narayanan, and Jaroslav Opatrny, Optimal Balancing of Satellite Queues in Packet Transmission to Ground Stations.

14:30 - 14:45

Jinsong Tan*, The Networked Common Goods Game.

Coffee Break

14:45 - 15:00

Session 10

Discrete Optimizations

(Chair: Ding-zhu Du)

15:00 - 15:15

Yilin Shen*, Dung T. Nguyen, and My T. Thai, On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs.

15:15 - 15:30

Cong Tian* and Zhenhua Duan, A Transformation from PPTL to S1S.

15:30 - 15:45

Bielecki Wlodzimierz , Klimek Tomasz, Palkowski Marek, and Anna Beletska*, An Iterative Algorithm of Computing The Transitive Closure of A Union of Parameterized Affine Integer Tuple Relations.

15:45 - 16:00

Deying Li*, Zheng Li, Wenkai Ma and Hong Chen, Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks.

16:00 - 16:15

Guanglong Yu*, Zhengke Miao, and Jinlong Shu, The Bases of Primitive Non-Powerful Sign Pattern Matrices.

16:15 - 16:30

Deying Li*, Zheng Li, Wenkai Ma, and Wenping Chen, Constrained Low-Interference Relay Node Deployment for Underwater Acoustic Wireless Sensor Networks.

17:00 - 19:00