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

✍ Scribed by Matthieu Latapy, Thi Ha Duong Phan (auth.), Weili Wu, Ovidiu Daescu (eds.)

• Publisher: Springer-Verlag Berlin Heidelberg
• Year: 2010
• Tongue: English
• Leaves: 437
• Series: Lecture Notes in Computer Science 6508 : Theoretical Computer Science and General Issues
• 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 -
Termination of Multipartite Graph Series Arising from Complex Network Modelling....Pages 1-10
Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids....Pages 11-20
Evacuation of Rectilinear Polygons....Pages 21-30
A Fast Algorithm for Powerful Alliances in Trees....Pages 31-40
NP-Completeness of Spreading Colored Points....Pages 41-50
Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach....Pages 51-64
Feasibility-Based Bounds Tightening via Fixed Points....Pages 65-76
A Characterisation of Stable Sets in Games with Transitive Preference....Pages 77-84
Linear Coherent Bi-cluster Discovery via Beam Detection and Sample Set Clustering....Pages 85-103
An Iterative Algorithm of Computing the Transitive Closure of a Union of Parameterized Affine Integer Tuple Relations....Pages 104-113
Bases of Primitive Nonpowerful Sign Patterns....Pages 114-127
Extended Dynamic Subgraph Statistics Using h -Index Parameterized Data Structures....Pages 128-141
Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets....Pages 142-156
Finding Strong Bridges and Strong Articulation Points in Linear Time....Pages 157-169
Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks....Pages 170-183
An Efficient Algorithm for Chinese Postman Walk on Bi-directed de Bruijn Graphs....Pages 184-196
On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs....Pages 197-211
Cyclic Vertex Connectivity of Star Graphs....Pages 212-221
The Number of Shortest Paths in the ( n , k )-Star Graphs....Pages 222-236
Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems....Pages 237-251
PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks....Pages 252-259
A Primal-Dual Approximation Algorithm for the Asymmetric Prize-Collecting TSP....Pages 260-269
Computing Toolpaths for 5-Axis NC Machines....Pages 270-284
A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs....Pages 285-299
A Randomized Algorithm for Weighted Approximation of Points by a Step Function....Pages 300-308
Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials....Pages 309-323
The Union of Colorful Simplices Spanned by a Colored Point Set....Pages 324-338
Compact Visibility Representation of 4-Connected Plane Graphs....Pages 339-353
Some Variations on Constrained Minimum Enclosing Circle Problem....Pages 354-368
Searching for an Axis-Parallel Shoreline....Pages 369-384
Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs....Pages 385-397
Scheduling Packets with Values and Deadlines in Size-Bounded Buffers....Pages 398-407
Transporting Jobs through a Processing Center with Two Parallel Machines....Pages 408-422
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