This book constitutes the refereed proceedings of the Second International Conference on Combinatorial Optimization and Applications, COCOA 2008, held in St. John's, Canada, in August 2008.
The 44 revised full papers were carefully reviewed and selected from 84 submissions. The papers feature original research in the areas of combinatorial optimization -- both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.
Author(s): Sebastian Böcker, Sebastian Briesemeister (auth.), Boting Yang, Ding-Zhu Du, Cao An Wang (eds.)
Series: Lecture Notes in Computer Science 5165 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2008
Language: English
Pages: 480
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Computer Communication Networks; Computer Graphics; Algorithms
Front Matter....Pages -
Going Weighted: Parameterized Algorithms for Cluster Editing....Pages 1-12
Parameterized Graph Editing with Chosen Vertex Degrees....Pages 13-22
Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries....Pages 23-31
Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets....Pages 32-42
Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems....Pages 43-53
A Parameterized Perspective on Packing Paths of Length Two....Pages 54-63
New Algorithms for k -Center and Extensions....Pages 64-78
Separating Sublinear Time Computations by Approximate Diameter....Pages 79-88
Computational Study on Dominating Set Problem of Planar Graphs....Pages 89-102
Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region....Pages 103-115
Parameterized Algorithms for Generalized Domination....Pages 116-126
Turán Graphs, Stability Number, and Fibonacci Index....Pages 127-138
Vertex-Uncertainty in Graph-Problems....Pages 139-148
Protean Graphs with a Variety of Ranking Schemes....Pages 149-159
Simplicial Powers of Graphs....Pages 160-170
On k - Versus ( k + 1)-Leaf Powers....Pages 171-179
Flows with Unit Path Capacities and Related Packing and Covering Problems....Pages 180-189
Strong Formulations for 2-Node-Connected Steiner Network Problems....Pages 190-200
Algorithms and Implementation for Interconnection Graph Problem....Pages 201-210
Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order....Pages 211-224
Fast Computation of Point-to-Point Paths on Time-Dependent Road Networks....Pages 225-234
Ant Colony Optimization Metaheuristic for the Traffic Grooming in WDM Networks....Pages 235-245
Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems....Pages 246-254
Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph....Pages 255-264
Improved Primal-Dual Approximation Algorithm for the Connected Facility Location Problem....Pages 265-277
Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs....Pages 278-285
An Improved Approximation Algorithm for the Capacitated Multicast Tree Routing Problem....Pages 286-295
Covering Arrays Avoiding Forbidden Edges....Pages 296-308
The Robot Cleans Up....Pages 309-318
On Recovering Syntenic Blocks from Comparative Maps....Pages 319-327
Automatic Generation of Symmetry-Breaking Constraints....Pages 328-338
On the Stable Set Polytope of Claw-Free Graphs....Pages 339-350
A Combinatorial Algorithm to Optimally Colour the Edges of the Graphs That Are Join of Regular Graphs....Pages 351-360
Magic Labelings on Cycles and Wheels....Pages 361-373
Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs....Pages 374-383
The Clique Corona Operation and Greedoids....Pages 384-392
On the Surface Area of the ( n , k )-Star Graph....Pages 393-404
Enumerating Isolated Cliques in Synthetic and Financial Networks....Pages 405-416
A Risk-Reward Competitive Analysis for the Recoverable Canadian Traveller Problem....Pages 417-426
Minimizing Total Completion Time in Two-Machine Flow Shops with Exact Delays....Pages 427-437
Efficient Method for Periodic Task Scheduling with Storage Requirement Minimization....Pages 438-447
Stochastic Online Scheduling Revisited....Pages 448-457
Delay Management Problem: Complexity Results and Robust Algorithms....Pages 458-468
Clustered SplitsNetworks....Pages 469-478
Back Matter....Pages -
