Combinatorial Optimization and Applications: 10th International Conference, COCOA 2016, Hong Kong, China, December 16–18, 2016, Proceedings

Front Matter....Pages I-XV
Front Matter....Pages 1-1
On the Capture Time of Cops and Robbers Game on a Planar Graph....Pages 3-17
The Mixed Evacuation Problem....Pages 18-32
A Comprehensive Reachability Evaluation for Airline Networks with Multi-constraints....Pages 33-48
Approximation and Hardness Results for the Max k-Uncut Problem....Pages 49-61
On Strong Tree-Breadth....Pages 62-76
Computing a Tree Having a Small Vertex Cover....Pages 77-91
Improved Precise Fault Diagnosis Algorithm for Hypercube-Like Graphs....Pages 92-106
Finding Disjoint Paths on Edge-Colored Graphs: A Multivariate Complexity Analysis....Pages 107-112
Total Dual Integrality of Triangle Covering....Pages 113-127
Time-Optimal Broadcasting of Multiple Messages in 1-in Port Model....Pages 128-143
Fast Searching on Complete k-partite Graphs....Pages 144-158
Cliques in Regular Graphs and the Core-Periphery Problem in Social Networks....Pages 159-174
Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem....Pages 175-186
An Introduction to Coding Sequences of Graphs....Pages 187-201
Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem....Pages 202-215
On the Complexity of Extracting Subtree with Keeping Distinguishability....Pages 216-229
Safe Sets in Graphs: Graph Classes and Structural Parameters....Pages 230-240
On Local Structures of Cubicity 2 Graphs....Pages 241-253
Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs....Pages 254-269
Front Matter....Pages 270-284
Algorithmic Aspects of Disjunctive Total Domination in Graphs....Pages 1-1
Instance Guaranteed Ratio on Greedy Heuristic for Genome Scaffolding....Pages 285-293
Front Matter....Pages 294-308
Performing Multicut on Walkable Environments....Pages 309-309
Minimum Weight Polygon Triangulation Problem in Sub-Cubic Time Bound....Pages 311-325
The Mixed Center Location Problem....Pages 326-339
Constrained Light Deployment for Reducing Energy Consumption in Buildings....Pages 340-349
On the 2-Center Problem Under Convex Polyhedral Distance Function....Pages 350-364
Algorithms for Colourful Simplicial Depth and Medians in the Plane....Pages 365-377
Realizability of Graphs as Triangle Cover Contact Graphs....Pages 378-392
A Quadratic Time Exact Algorithm for Continuous Connected 2-Facility Location Problem in Trees (Extended Abstract)....Pages 393-407
Front Matter....Pages 408-420
Algorithmic Analysis for Ridesharing of Personal Vehicles....Pages 421-421
On the Complexity of Bounded Deletion Propagation....Pages 423-437
On Residual Approximation in Solution Extension Problems....Pages 438-452
On the Parameterized Parallel Complexity and the Vertex Cover Problem....Pages 453-462
A Linear Potential Function for Pairing Heaps....Pages 463-476
Amortized Efficiency of Ranking and Unranking Left-Child Sequences in Lexicographic Order....Pages 477-488
Front Matter....Pages 489-504
Optimal Speed Scaling with a Solar Cell....Pages 505-518
An Approximation Algorithm for the k-Median Problem with Uniform Penalties via Pseudo-Solutions....Pages 519-519
On-Line Pattern Matching on Uncertain Sequences and Applications....Pages 521-535
Front Matter....Pages 536-546
Scheduling with Interjob Communication on Parallel Processors....Pages 547-562
Cost-Efficient Scheduling on Machines from the Cloud....Pages 519-519
Strategic Online Facility Location....Pages 563-577
An Efficient PTAS for Parallel Machine Scheduling with Capacity Constraints....Pages 578-592
A Pseudo-Polynomial Time Algorithm for Solving the Knapsack Problem in Polynomial Space....Pages 593-607
Front Matter....Pages 608-623
An Incentive Mechanism for Selfish Bin Covering....Pages 624-638
Congestion Games with Mixed Objectives....Pages 639-639
An Optimal Strategy for Static Black-Peg Mastermind with Two Pegs....Pages 641-654
Front Matter....Pages 655-669
The Incentive Ratio in Exchange Economies....Pages 670-682
Solving Dynamic Vehicle Routing Problem with Soft Time Window by iLNS and hPSO....Pages 683-683
Convex Independence in Permutation Graphs....Pages 685-692
The Connected p-Center Problem on Cactus Graphs....Pages 693-701
Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem....Pages 702-709
Using Unified Model Checking to Verify Heaps....Pages 710-717
A Filtering Heuristic for the Computation of Minimum-Volume Enclosing Ellipsoids....Pages 718-725
Relaxations of Discrete Sets with Semicontinuous Variables....Pages 726-734
Unfolding the Core Structure of the Reciprocal Graph of a Massive Online Social Network....Pages 735-743
Tackling Common Due Window Problem with a Two-Layered Approach....Pages 744-753
A Polynomial Time Solution for Permutation Scaffold Filling....Pages 754-762
Back Matter....Pages 763-771
....Pages 772-781