Combinatorial Algorithms

1. Front Matter

   PDF

2. Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes

   • Konrad Dabrowski, Vadim Lozin, Haiko Müller, Dieter Rautenbach

   Pages 1-9

3. On the Maximal Sum of Exponents of Runsin a String

   • Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

   Pages 10-19

4. Path-Based Supports for Hypergraphs

   • Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud Sallaberry

   Pages 20-33

5. On Improved Exact Algorithms for L(2,1)-Labeling of Graphs

   • Konstanty Junosza-Szaniawski, Paweł Rzążewski

   Pages 34-37

6. Thread Graphs, Linear Rank-Width and Their Algorithmic Applications

   • Robert Ganian

   Pages 38-42

7. Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three

   • Francine Blanchet-Sadri, Bob Chen, Aleksandar Chakarov

   Pages 43-55

8. Shortest Paths between Shortest Paths and Independent Sets

   • Marcin Kamiński, Paul Medvedev, Martin Milanič

   Pages 56-67

9. Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism

   • Yusaku Kaneta, Hiroki Arimura

   Pages 68-81

10. Dichotomy for Coloring of Dart Graphs

    • Martin Kochol, Riste Škrekovski

    Pages 82-89

11. Worst Case Efficient Single and Multiple String Matching in the RAM Model

    • Djamal Belazzougui

    Pages 90-102

12. The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Δ + 2

    • Toru Hasunuma, Toshimasa Ishii, Hirotaka Ono, Yushi Uno

    Pages 103-106

13. Upper and Lower I/O Bounds for Pebbling r-Pyramids

    • Desh Ranjan, John Savage, Mohammad Zubair

    Pages 107-120

14. Single Parameter FPT-Algorithms for Non-trivial Games

    • Vladimir Estivill-Castro, Mahdi Parsa

    Pages 121-124

15. The Complexity Status of Problems Related to Sparsest Cuts

    • Paul Bonsma, Hajo Broersma, Viresh Patel, Artem Pyatkin

    Pages 125-135

16. On Approximation Complexity of Metric Dimension Problem

    • Mathias Hauptmann, Richard Schmied, Claus Viehmann

    Pages 136-139

17. Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates

    • Alfredo Navarra, Cristina M. Pinotti

    Pages 140-153

18. Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures

    • Cristina Bazgan, Sonia Toubaline, Zsolt Tuza

    Pages 154-166

19. Computing Role Assignments of Proper Interval Graphs in Polynomial Time

    • Pinar Heggernes, Pim van ’t Hof, Daniël Paulusma

    Pages 167-180

20. Efficient Connectivity Testing of Hypercubic Networks with Faults

    • Tomáš Dvořák, Jiří Fink, Petr Gregor, Václav Koubek, Tomasz Radzik

    Pages 181-191

This book constitutes the thoroughly referred post-proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, held in London, UK, in July 2010.
The 31 revised full papers presented together with extended abstracts of 8 poster presentations were carefully reviewed and selected from a total of 85 submissions. A broad variety of combinatorial graph algorithms for the computations of various graph features are presented; also algorithms for network compuation, approximation, computational geometry, games, and search are presented and complexity aspects of such algorithms are discussed.

• combinatorial enumeration
• computational complexity
• graph coloring
• graph labeling
• hypergraphs
• matrix computation
• network routing alorithms
• parameterized algorithms
• parameterized complexity
• problem complexity
• shortest path computation
• string matching
• tree matching
• algorithm analysis and problem complexity
• data structures

• Department of Computer Science, University of London, King’s College, London, UK

  Costas S. Iliopoulos

• Department of Computing and Software, McMaster University, Hamilton, Canada

  William F. Smyth

Policies and ethics