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

by Costas S. Iliopoulos (Editor), William F. Smyth (Editor)

Overview

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.

Product Details

ISBN-13:	9783642192210
Publisher:	Springer Berlin Heidelberg
Publication date:	05/03/2011
Series:	Lecture Notes in Computer Science , #6460
Edition description:	2011
Pages:	418
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Table of Contents

Parameterized algorithams for the independent set problem in some hereditary graph classes Konrad Dabrowski Vadim Lozin Haiko Müller Dieter Routenbach 1

On the maximal Sum of Exponents of Runs in a String Maxime Crochemore Marcin Kubica Jakub Radoszewski Wojciech Rytter Tomasz Walen 10

Path-Based Supports for Hypergraphs Ulrik Brandes Sabine Cornelsen Barbara Pampel Arnaud Sallaberry

On Improved Exact Algorithms for L(2, 1)-Labeling of Graphs Konstanty Junosza-Szaniawski Pawel Rz&acedil;zewski

Thread graphs, linear Rank-Width and Their Algorithmic Applications Robert Ganian 38

Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three Francine Blanchet-Sadri Bob Chen Aleksandar Chakarav 43

Shortest paths between shortest paths and independent sets Marcin Kaninski Paul Medvedev Martin Milanič 56

Faster Bit-Parrallel Algorithams for Unordered Pseudo-tree Matching and Tree Homeomorphism Yusaku kaneta Hiroki Arimura 68

Dichotomy for coloring of dart graphs Martin Kochol Riste ˇSkrekovski 82

Worst case efficient single and multiple string matching in the RAM model Djamal Belazzougui 90

The (2,1)-Total Labelimg Number of Outerplanar Graphs is at most Δ + 2 Toru Hasunuma Toshimasa Ishn Hirotaka Ona Yushi Uno 103

Upper and lower I/O Bounds for Pebbling r-pyramids Desh Ranjan John Savage Mohammad Zubair 107

Single Parameter FPT-Algorithms for Non-trivial Games Vladimir Estimil-Castro Mahdi Parsa 121

The Complexity Status of Problems Related to Sparsest Cuts Paul Bonsma Hajo Broersma Viresh Patel Artem Pyatkin 125

On Approximation Complexity of Metric Dimension Problem Mathias Hauptmann Richard Schmied Claus Viehmann 136

Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates Alfredo Navarra Cristina M. Pinotti 140

Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures Cristina Bazgan Sonia Toubaline Zsolt Tuza 154

Computing Role Assignments of Proper Interval Graphs in Polynomial Time Pinar Heggernes Pim van 't Hof Daniel Paulusma 167

Efficient Connectivity Testing of Hypercubic Networks with Faults Tomáš Dvorák Jirí Fink Petr Gregor Václav Koubek Tomasz Radrik 181

Reductions of Matrices Associated with Nowhere-Zero flows Martin Kochol Nad'a Krivonáková Silvia Smejová Katarína Šranková 192

Blocks of Hypergraphs: Applied to Hypergraphs and Outerplanarity Ulrik Brandes Sabine Cornelsen Barbara Pampel Arnaud sallaberry 201

Testing the Simultaneous Embeddability of Two Graphs Whose intersection Is a Biconnected Graph or a Tree Patrizio Angelini Giuseppe Di Battista Fabrizio Frati Maurizio Patrignani Ignaz Rutter 212

Skip Lift: A Probabilistic Alternative to Red-Black Trees Prosenjit Bose Karim Douïeb Douieb Pat Morin 226

On a relationship between Completely Separating Systems and Antimagic labeling of Regular Graphs Oudone Phanalasy Mirka Miller Leanne Rylands Paulette Lieby 238

Parameterized Complexity of k-Anonymity: Hardness and Tractability Paola Bonizzoni Gianluca Della Vedova Riccardo Dondi Yuri Pirola 242

On fast Enummeration of Pseudo Bicliques Zareen Alamgir Saira Karim Syed Husnine 256

Efficient Chaining of seeds in Ordered Trees Julien Allali Cedric Chauue Pascal Ferraro Anne-Laure Gaillard 260

On the Computational Complexity of Degenerate Unit Distance Representations of Graphs Boris Horvat Jan Kratochvíl Tomož Pisanski 274

Recognition of Probe Ptolemaic Graphs(Ectended Abstract) Maw-Shang Chang Ling-Ju Hung 286

Graphs of Separability at Most Two: Structural Characterizations and Their Consequences Ferdinando Cicalese Martin Milanič 291

On Antimagic Labing for Generalized Web and Flower Graphs Joe Ryan Oudone Phanalasy Mirka Miller Leanne Rylands 303

Chains-into-Bins processes Tugkan Batu Petra Berenbrink Colin Cooper 314

Complexity of Locality Injective Homomorphism to the Theta Graphs Bernard Lidický Marek Tesar 326

Ranking and Drawing in Suberponential Time Henning Fernau Fedor V. Fomin Daniel Lokshtanon Matthias Mnich Geevarghese Philip Saket Saurabh 337

Efficient Reconstruction of RC-Equivalent strings Ferdinando Cicalese Péter L. Erdos Zsuzsanna Lipták 349

Improved Points Approximation Algorithms Based on Simplical Thickness Data Structures Danny Z. Chen Haitao Wang 363

The Cover Time of Cartesian Product Graphs Mohammed Abdullah Colin Cooper Tomasz Radzik 377

Dictionary-Symbolwise Flexible Parsing Maxime Crochemore Laura Giambruno Alessio Langiu Filippo Mignosi Antonio Restivo 390

Regular Language Constrained Sequence Alignment Eevisited Gregory Kucherov Tomar Pinhas Michal Ziv-Ukelson 404

Author index 417