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

✍ Scribed by T-H. Hubert Chan, Minming Li, Lusheng Wang (eds.)

• Publisher: Springer International Publishing
• Year: 2016
• Tongue: English
• Leaves: 800
• Series: Lecture Notes in Computer Science 10043
• Edition: 1
• Category: Library

✦ Synopsis

This book constitutes the refereed proceedings of the 10th International Conference on Combinatorial Optimization and Applications, COCOA 2016, held in Hong Kong, China, in December 2016.

The 60 full papers included in the book were carefully reviewed and selected from 122 submissions. The papers are organized in topical sections such as graph theory, geometric optimization, complexity and data structure, combinatorial optimization, and miscellaneous.

✦ Table of Contents

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

✦ Subjects

Algorithm Analysis and Problem Complexity;Discrete Mathematics in Computer Science;Numeric Computing;Algorithms;Computer Communication Networks;Computer Graphics