Combinatorial Optimization and Applications: 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Proceedings, Part II

✍ Scribed by Brad Ballinger, Nadia Benbernou (auth.), Weili Wu, Ovidiu Daescu (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2010
• Tongue: English
• Leaves: 428
• Series: Lecture Notes in Computer Science 6509
• Edition: 1
• Category: Library

✦ Synopsis

The 4th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2010) took place in Big Island, Hawaii, USA, December 18–20, 2010. Past COCOA conferences were held in Xi’an, China (2007), Newfoundland, Canada (2008)and Huangshan, China (2009). COCOA2010providedaforumforresearchersworkingintheareasofcom- natorial optimization and its applications. In addition to theoretical results, the conference also included recent works on experimental and applied research of general algorithmic interest. The Program Committee received 108 submissions from more than 23 countries and regions, including Australia, Austria, Canada, China, Denmark, France, Germany, Hong Kong, India, Italy, Japan, Korea, Mexico, New Zealand, Poland, Slovak Republic, Spain, Sweden, Switzerland, Taiwan, UK, USA, Vietnam, etc. Among the 108 submissions, 49 regular papers were selected for presentation at the conference and are included in this volume. Some of these papers will be selected for publication in a special issue of the Journal of Combinatorial Optimization, a special issue of Theoretical Computer Science, a special issue of Optimization Letters, and a special issue of Discrete Mathematics, Algorithms and Applications under the standard refereeing procedure.

✦ Table of Contents

Front Matter....Pages -
Coverage with k -Transmitters in the Presence of Obstacles....Pages 1-15
On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem....Pages 16-30
Reducing the Maximum Latency of Selfish Ring Routing via Pairwise Cooperations....Pages 31-45
Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks....Pages 46-57
Time Optimal Algorithms for Black Hole Search in Rings....Pages 58-71
Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle....Pages 72-86
A Constant-Factor Approximation Algorithm for the Link Building Problem....Pages 87-96
XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme....Pages 97-106
Computational Study for Planar Connected Dominating Set Problem....Pages 107-116
Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives....Pages 117-130
A Search-Based Approach to the Railway Rolling Stock Allocation Problem....Pages 131-143
Approximation Algorithm for the Minimum Directed Tree Cover....Pages 144-159
An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs....Pages 160-169
A New Result on [ k , k  + 1]-Factors Containing Given Hamiltonian Cycles....Pages 170-180
Yao Graphs Span Theta Graphs....Pages 181-194
A Simpler Algorithm for the All Pairs Shortest Path Problem with O ( n 2 log n ) Expected Time....Pages 195-206
New Min-Max Theorems for Weakly Chordal and Dually Chordal Graphs....Pages 207-218
A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem....Pages 219-227
Fast Edge-Searching and Related Problems....Pages 228-242
Diameter-Constrained Steiner Tree....Pages 243-253
Minimizing the Maximum Duty for Connectivity in Multi-Interface Networks....Pages 254-267
A Divide-and-Conquer Algorithm for Computing a Most Reliable Source on an Unreliable Ring-Embedded Tree....Pages 268-280
Constrained Low-Interference Relay Node Deployment for Underwater Acoustic Wireless Sensor Networks....Pages 281-291
Structured Overlay Network for File Distribution....Pages 292-302
Optimal Balancing of Satellite Queues in Packet Transmission to Ground Stations....Pages 303-316
The Networked Common Goods Game....Pages 317-331
A Novel Branching Strategy for Parameterized Graph Modification Problems....Pages 332-346
Listing Triconnected Rooted Plane Graphs....Pages 347-361
Bipartite Permutation Graphs Are Reconstructible....Pages 362-373
A Transformation from PPTL to S1S....Pages 374-386
Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs....Pages 387-400
Approximate Ellipsoid in the Streaming Model....Pages 401-413
Back Matter....Pages -

✦ Subjects

Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computer Communication Networks; Computer Graphics; Computational Biology/Bioinformatics; Symbolic and Algebraic Manipulation