Combinatorial Optimization and Applications

1. Front Matter

   PDF

2. Termination of Multipartite Graph Series Arising from Complex Network Modelling

   • Matthieu Latapy, Thi Ha Duong Phan, Christophe Crespelle, Thanh Qui Nguyen

   Pages 1-10

3. Simple Cuts Are Fast and Good: Optimum Right-Angled Cuts in Solid Grids

   • Andreas Emil Feldmann, Shantanu Das, Peter Widmayer

   Pages 11-20

4. Evacuation of Rectilinear Polygons

   • Sándor Fekete, Chris Gray, Alexander Kröller

   Pages 21-30

5. A Fast Algorithm for Powerful Alliances in Trees

   • Ararat Harutyunyan

   Pages 31-40

6. NP-Completeness of Spreading Colored Points

   • Ovidiu Daescu, Wenqi Ju, Jun Luo

   Pages 41-50

7. Construction of Mixed Covering Arrays of Variable Strength Using a Tabu Search Approach

   • Loreto Gonzalez-Hernandez, Nelson Rangel-Valdez, Jose Torres-Jimenez

   Pages 51-64

8. Feasibility-Based Bounds Tightening via Fixed Points

   • Pietro Belotti, Sonia Cafieri, Jon Lee, Leo Liberti

   Pages 65-76

9. A Characterisation of Stable Sets in Games with Transitive Preference

   • Takashi Matsuhisa

   Pages 77-84

10. Linear Coherent Bi-cluster Discovery via Beam Detection and Sample Set Clustering

    • Yi Shi, Maryam Hasan, Zhipeng Cai, Guohui Lin, Dale Schuurmans

    Pages 85-103

11. 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

    Pages 104-113

12. Bases of Primitive Nonpowerful Sign Patterns

    • Guanglong Yu, Zhengke Miao, Jinlong Shu

    Pages 114-127

13. Extended Dynamic Subgraph Statistics Using h-Index Parameterized Data Structures

    • David Eppstein, Michael T. Goodrich, Darren Strash, Lowell Trott

    Pages 128-141

14. Discrete Optimization with Polynomially Detectable Boundaries and Restricted Level Sets

    • Yakov Zinder, Julia Memar, Gaurav Singh

    Pages 142-156

15. Finding Strong Bridges and Strong Articulation Points in Linear Time

    • Giuseppe F. Italiano, Luigi Laura, Federico Santaroni

    Pages 157-169

16. Robust Optimization of Graph Partitioning and Critical Node Detection in Analyzing Networks

    • Neng Fan, Panos M. Pardalos

    Pages 170-183

17. An Efficient Algorithm for Chinese Postman Walk on Bi-directed de Bruijn Graphs

    • Vamsi Kundeti, Sanguthevar Rajasekaran, Heiu Dinh

    Pages 184-196

18. On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs

    • Yilin Shen, Dung T. Nguyen, My T. Thai

    Pages 197-211

19. Cyclic Vertex Connectivity of Star Graphs

    • Zhihua Yu, Qinghai Liu, Zhao Zhang

    Pages 212-221

20. The Number of Shortest Paths in the (n, k)-Star Graphs

    • Eddie Cheng, Ke Qiu, Zhi Zhang Shen

    Pages 222-236

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.

• Processing
• Scheduling
• algorithms
• approximation algorithms
• bioinformatics
• cloud computing
• combinatorial optimization
• combinatorics
• complexity
• computational algebra
• computational biology
• computational financing
• computational game theory
• computational learning theory
• data structures
• algorithm analysis and problem complexity

• Department of Computer Science, University of Texas at Dallas, Richardson, USA

  Weili Wu, Ovidiu Daescu

Policies and ethics