Combinatorial Algorithms: 21st International Workshop, Iwoca 2010, London, Uk, July 26-28, 2010, Revised Selected Papers - Lecture Notes in Computer Science / Theoretical Computer Science and General Issues

Marc Notes: Proceedings of the 21st International Workshop on Combinatorial Algorithms, IWOCA 2010, held in London, UK, in July 2010.; Based on publisher-provided data. Table of Contents: Parameterized algorithams for the independent set problem in some hereditary graph classes / Konrad Dabrowski, Vadim Lozin, Haiko MUller, Dieter Routenbach -- On the maximal Sum of Exponents of Runs in a String / Maxime Crochemore, Marcin Kubica, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen -- 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 -- Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three / Francine Blanchet-Sadri, Bob Chen, Aleksandar Chakarav -- Shortest paths between shortest paths and independent sets / Marcin Kaninski, Paul Medvedev, Martin Milanič -- Faster Bit-Parrallel Algorithams for Unordered Pseudo-tree Matching and Tree Homeomorphism / Yusaku kaneta, Hiroki Arimura -- Dichotomy for coloring of dart graphs / Martin Kochol, Riste ˇ Skrekovski -- Worst case efficient single and multiple string matching in the RAM model / Djamal Belazzougui -- The (2,1)-Total Labelimg Number of Outerplanar Graphs is at most ? + 2 / Toru Hasunuma, Toshimasa Ishn, Hirotaka Ona, Yushi Uno -- Upper and lower I/O Bounds for Pebbling r-pyramids / Desh Ranjan, John Savage, Mohammad Zubair -- 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 -- On Approximation Complexity of Metric Dimension Problem / Mathias Hauptmann, Richard Schmied, Claus Viehmann -- Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates / Alfredo Navarra, Cristina M. Pinotti -- Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures / Cristina Bazgan, Sonia Toubaline, Zsolt Tuza -- Computing Role Assignments of Proper Interval Graphs in Polynomial Time / Pinar Heggernes, Pim van 't Hof, Daniel Paulusma -- Efficient Connectivity Testing of Hypercubic Networks with Faults / TomAS DvorAk, JirI Fink, Petr Gregor, VAclav Koubek, Tomasz Radrik -- Reductions of Matrices Associated with Nowhere-Zero flows / Martin Kochol, Nad'a KrivonAkovA, Silvia SmejovA, KatarIna SrankovA -- Blocks of Hypergraphs: Applied to Hypergraphs and Outerplanarity / Ulrik Brandes, Sabine Cornelsen, Barbara Pampel, Arnaud sallaberry -- 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 -- Skip Lift: A Probabilistic Alternative to Red-Black Trees / Prosenjit Bose, Karim DouIeb Douieb, Pat Morin -- On a relationship between Completely Separating Systems and Antimagic labeling of Regular Graphs / Oudone Phanalasy, Mirka Miller, Leanne Rylands, Paulette Lieby -- Parameterized Complexity of k-Anonymity: Hardness and Tractability / Paola Bonizzoni, Gianluca Della Vedova, Riccardo Dondi, Yuri Pirola -- On fast Enummeration of Pseudo Bicliques / Zareen Alamgir, Saira Karim, Syed Husnine -- Efficient Chaining of seeds in Ordered Trees / Julien Allali, Cedric Chauue, Pascal Ferraro, Anne-Laure Gaillard -- On the Computational Complexity of Degenerate Unit Distance Representations of Graphs / Boris Horvat, Jan KratochvIl, Tomož Pisanski -- Recognition of Probe Ptolemaic Graphs(Ectended Abstract) / Maw-Shang Chang, Ling-Ju Hung -- Graphs of Separability at Most Two: Structural Characterizations and Their Consequences / Ferdinando Cicalese, Martin Milanič -- On Antimagic Labing for Generalized Web and Flower Graphs / Joe Ryan, Oudone Phanalasy, Mirka Miller, Leanne Rylands -- Chains-into-Bins processes / Tugkan Batu, Petra Berenbrink, Colin Cooper -- Complexity of Locality Injective Homomorphism to the Theta Graphs / Bernard LidickY, Marek Tesar -- Ranking and Drawing in Suberponential Time / Henning Fernau, Fedor V. Fomin, Daniel Lokshtanon, Matthias Mnich, Geevarghese Philip, Saket Saurabh -- Efficient Reconstruction of RC-Equivalent strings / Ferdinando Cicalese, PEter L. Erdos, Zsuzsanna LiptAk -- Improved Points Approximation Algorithms Based on Simplical Thickness Data Structures / Danny Z. Chen, Haitao Wang -- The Cover Time of Cartesian Product Graphs / Mohammed Abdullah, Colin Cooper, Tomasz Radzik -- Dictionary-Symbolwise Flexible Parsing / Maxime Crochemore, Laura Giambruno, Alessio Langiu, Filippo Mignosi, Antonio Restivo -- Regular Language Constrained Sequence Alignment Eevisited / Gregory Kucherov, Tomar Pinhas, Michal Ziv-Ukelson -- Author index. Publisher Marketing: 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.