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

by Weili Wu (Editor), Ovidiu Daescu (Editor)

Overview

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). COCOA 2010 provided a forum for researchers working in the areas of com- 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.

Product Details

ISBN-13:	9783642174575
Publisher:	Springer Berlin Heidelberg
Publication date:	03/09/2011
Series:	Lecture Notes in Computer Science , #6508
Edition description:	2010
Pages:	424
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Table of Contents

Termination of Multipartite Graph Series Arising from Complex Network Modelling Matthieu Latapy Thi Ha Duong Phan Christophe Crespelle Thanh Qui Nguyen 1

Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids Andreas Emil Feldmann Shantanu Das Peter Widmayer 11

Evacuation of Rectilinear Polygons Sándor Fekete Chris Gray Alexander Kröller 21

A Fast Algorithm of for Powerful Alliances in Trees Ararat Harutyunyan 31

NP-Completeness of Spreading Colored Points Ovidiu Daescu Wenqi Ju Jun Luo 41

Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach Loreto Gonzalez-Hernandez Nelson Rangel-Valdez Jose Torres-Jimenez 51

Feasibility-Based Bounds Tightening via Fixed Points Pietro Belotti Sonia Cafieri Jon Lee Leo Liberti 65

A Characterisation of Stable Sets in Games with Transitive Preference Takashi Matsuhisa 77

Linear Coherent Bi-cluster Discovery via Beam Detection and Sample Set Clustering Yi Shi Maryam Hasan Zhipeng Cai Guohui Lin Dale Schuurmans 85

An Iterative Algorithm of Computing the Transitive Closure of a Union of Parameterized Affine Integer Tuple Relations Bielecki Wlodzimierz Klimek Tomasz Palkowski Marek Anna Beletska 104

Bases of Primitive Nonpowerful Sign Patterns Guanglong Yu Zhengke Miao Jinlong Shu 114

Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures David Eppstein Michael T. Goodrich Darren Strash Lowell Trott 128

Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets Yakov Zinder Julia Memar Gaurav Singh 142

Finding Strong Bridges and Strong Articulation Points in Linear Time Giuseppe F. Italiano Luigi Laura Federico Santaroni 157

Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks Neng Fan Panos M. Pardalos 170

An Efficient Algorithm for Chinese Postman Walk on Bi-directed de Bruijn Graphs Vamsi Kundeti Sanguthevar Rajasekaran Heiu Dinh 184

On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs Yilin Shen Dung T. Nguyen My T. Thai 197

Cyclic Vertex Connectivity of Star Graphs Zhihua Yu Qinghai Liu Zhao Zhang 212

The Number of Shortest Paths in the (n, k)-Star Graphs Eddie Cheng Ke Qiu Zhi Zhang Shen 222

Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems Cristina Bazgan Sonia Toubaline Daniel Vanderpooten 237

PTAS for Minimum Connected Dominating Set with Routing Cost Constraint in Wireless Sensor Networks Hongwei Du Qiang Ye Jioafei Zhong Yuexuan Wang Wonjun Lee Haesun Park 252

A Primal-Dual Approximation Algorithm for the Asymmetric Prize-Collecting TSP Viet Hung Nguyen 260

Computing Toolpaths for 5-Axis NC Machines Danny Z. Chen Ewa Misiotek 270

A Trichotomy Theorem for the Approximate Counting of Complex-Weighted Bounded-Degree Boolean CSPs Tomoyuki Yamakami 285

A Randomized Algorithm for Weighted Approximation of Points by a Step Function Jin-Yi Liu 300

Approximating Multilinear Monomial Coefficients and Maximum Multilinear Monomials in Multivariate Polynomials Zhixiang Chen Bin Fu 309

The Union of Colorful Simplices Spanned by a Colored Point Set André Schulz Csaba D. Tóth 324

Compact Visibility Representation of 4-Connected Plane Graphs Xin He Jiun-Jie Wang Huaming Zhang 339

Some Variations on Constrained Minimum Enclosing Circle Problem Arindam Karmakar Sandip Das Subhas C. Nandy Binay K. Bhattacharya 354

Searching for an Axis-Parallel Shoreline Elmar Langetepe 369

Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs Evangelos Kranakis Danny Krizanc Oscar Morales Ponce Ladislav Stacho 385

Scheduling Packets with Values and Deadlines in Size-Bounded Buffers Fei Li 398

Transporting Jobs through a Processing Center with Two Parallel Machines Hans Kellerer Alan J. Soper Vitaly A. Strusevich 408

Author Index 423