Combinatorial Optimization and Applications

1. Front Matter

   PDF

2. Coverage with k-Transmitters in the Presence of Obstacles

   • Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmović et al.

   Pages 1-15

3. On Symbolic OBDD-Based Algorithms for the Minimum Spanning Tree Problem

   • Beate Bollig

   Pages 16-30

4. Reducing the Maximum Latency of Selfish Ring Routing via Pairwise Cooperations

   • Xujin Chen, Xiaodong Hu, Weidong Ma

   Pages 31-45

5. Constrained Surface-Level Gateway Placement for Underwater Acoustic Wireless Sensor Networks

   • Deying Li, Zheng Li, Wenkai Ma, Hong Chen

   Pages 46-57

6. Time Optimal Algorithms for Black Hole Search in Rings

   • Balasingham Balamohan, Paola Flocchini, Ali Miri, Nicola Santoro

   Pages 58-71

7. Strong Connectivity in Sensor Networks with Given Number of Directional Antennae of Bounded Angle

   • Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Jaroslav Opatrny, Oscar Morales Ponce, Ladislav Stacho

   Pages 72-86

8. A Constant-Factor Approximation Algorithm for the Link Building Problem

   • Martin Olsen, Anastasios Viglas, Ilia Zvedeniouk

   Pages 87-96

9. XML Reconstruction View Selection in XML Databases: Complexity Analysis and Approximation Scheme

   • Artem Chebotko, Bin Fu

   Pages 97-106

10. Computational Study for Planar Connected Dominating Set Problem

    • Marjan Marzban, Qian-Ping Gu, Xiaohua Jia

    Pages 107-116

11. Bounds for Nonadaptive Group Tests to Estimate the Amount of Defectives

    • Peter Damaschke, Azam Sheikh Muhammad

    Pages 117-130

12. A Search-Based Approach to the Railway Rolling Stock Allocation Problem

    • Tomoshi Otsuki, Hideyuki Aisu, Toshiaki Tanaka

    Pages 131-143

13. Approximation Algorithm for the Minimum Directed Tree Cover

    • Viet Hung Nguyen

    Pages 144-159

14. An Improved Approximation Algorithm for Spanning Star Forest in Dense Graphs

    • Jing He, Hongyu Liang

    Pages 160-169

15. A New Result on [k,k + 1]-Factors Containing Given Hamiltonian Cycles

    • Guizhen Liu, Xuejun Pan, Jonathan Z. Sun

    Pages 170-180

16. Yao Graphs Span Theta Graphs

    • Mirela Damian, Kristin Raudonis

    Pages 181-194

17. A Simpler Algorithm for the All Pairs Shortest Path Problem with O(n ²logn) Expected Time

    • Tadao Takaoka, Mashitoh Hashim

    Pages 195-206

18. New Min-Max Theorems for Weakly Chordal and Dually Chordal Graphs

    • Arthur H. Busch, Feodor F. Dragan, R. Sritharan

    Pages 207-218

19. A Simpler and More Efficient Algorithm for the Next-to-Shortest Path Problem

    • Bang Ye Wu

    Pages 219-227

20. Fast Edge-Searching and Related Problems

    • Boting Yang

    Pages 228-242

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.

• Blu-ray
• algorithms
• approximation algorithms
• bioinformatics
• cloud computing
• combinatorial optimization
• combinatorics
• complexity
• computational algebra
• computational biology
• computational financing
• computational game theory
• computational geometry
• computational learning theory
• databases
• algorithm analysis and problem complexity

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

  Weili Wu, Ovidiu Daescu

Policies and ethics