Combinatorial Optimization and Applications

1. Front Matter

   PDF

2. Going Weighted: Parameterized Algorithms for Cluster Editing

   • Sebastian Böcker, Sebastian Briesemeister, Quang B. A. Bui, Anke Truss

   Pages 1-12

3. Parameterized Graph Editing with Chosen Vertex Degrees

   • Luke Mathieson, Stefan Szeider

   Pages 13-22

4. Fixed-Parameter Tractability of Anonymizing Data by Suppressing Entries

   • Rhonda Chaytor, Patricia A. Evans, Todd Wareham

   Pages 23-31

5. Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets

   • Peter Damaschke

   Pages 32-42

6. Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems

   • Nadja Betzler, Johannes Uhlmann

   Pages 43-53

7. A Parameterized Perspective on Packing Paths of Length Two

   • Henning Fernau, Daniel Raible

   Pages 54-63

8. New Algorithms for k-Center and Extensions

   • René Brandenberg, Lucia Roth

   Pages 64-78

9. Separating Sublinear Time Computations by Approximate Diameter

   • Bin Fu, Zhiyu Zhao

   Pages 79-88

10. Computational Study on Dominating Set Problem of Planar Graphs

    • Marjan Marzban, Qian-Ping Gu, Xiaohua Jia

    Pages 89-102

11. Optimal Movement of Mobile Sensors for Barrier Coverage of a Planar Region

    • B. Bhattacharya, B. Burmester, Y. Hu, E. Kranakis, Q. Shi, A. Wiese

    Pages 103-115

12. Parameterized Algorithms for Generalized Domination

    • Venkatesh Raman, Saket Saurabh, Sriganesh Srihari

    Pages 116-126

13. Turán Graphs, Stability Number, and Fibonacci Index

    • Véronique Bruyère, Hadrien Mélot

    Pages 127-138

14. Vertex-Uncertainty in Graph-Problems

    • Cécile Murat, Vangelis Th. Paschos

    Pages 139-148

15. Protean Graphs with a Variety of Ranking Schemes

    • Paweł Prałat

    Pages 149-159

16. Simplicial Powers of Graphs

    • Andreas Brandstädt, Van Bang Le

    Pages 160-170

17. On k- Versus (k + 1)-Leaf Powers

    • Andreas Brandstädt, Peter Wagner

    Pages 171-179

18. Flows with Unit Path Capacities and Related Packing and Covering Problems

    • Maren Martens, Martin Skutella

    Pages 180-189

19. Strong Formulations for 2-Node-Connected Steiner Network Problems

    • Markus Chimani, Maria Kandyba, Ivana Ljubić, Petra Mutzel

    Pages 190-200

20. Algorithms and Implementation for Interconnection Graph Problem

    • Hongbing Fan, Christian Hundt, Yu-Liang Wu, Jason Ernst

    Pages 201-210

This book constitutes the refereed proceedings of the Second International Conference on Combinatorial Optimization and Applications, COCOA 2008, held in St. John's, Canada, in August 2008. The 44 revised full papers were carefully reviewed and selected from 84 submissions. The papers feature original research in the areas of combinatorial optimization -- both theoretical issues and and applications motivated by real-world problems thus showing convincingly the usefulness and efficiency of the algorithms discussed in a practical setting.

• algorithm
• algorithms
• ant colony optimization
• approximation
• bioinformatics
• classification
• combinatorial optimization
• competitive analysis
• complexity theory
• computational biology
• computational complexity
• computational discrete mathematics
• computational fin
• optimization
• algorithm analysis and problem complexity

Policies and ethics