Skip to main content
SpringerLink
Log in
Book cover

Combinatorial Algorithms

21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers

  • Conference proceedings
  • © 2011

Overview

Editors:
  1. Costas S. Iliopoulos

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

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. William F. Smyth

    1. Department of Computing and Software, McMaster University, Hamilton, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  • High quality selected papers
  • Unique visibility
  • State of the art research

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 6460)

Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)

Included in the following conference series:

Conference proceedings info: IWOCA 2010.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (39 papers)

  1. Front Matter

    Download chapter 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
Back to top

Other volumes

  1. Combinatorial Algorithms

Keywords

About this book

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.

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation