Combinatorial Algorithms

by Iliopoulos, Costas S.; Smyth, William F.

• ISBN13: 9783642192210
• ISBN10: 3642192211
• Format: Paperback
• Copyright: 2011-05-03
• Publisher: Springer Nature

Summary

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.

Table of Contents

Parameterized algorithams for the independent set problem in some hereditary graph classes	p. 1
On the maximal Sum of Exponents of Runs in a String	p. 10
Path-Based Supports for Hypergraphs
On Improved Exact Algorithms for L(2, 1)-Labeling of Graphs
Thread graphs, linear Rank-Width and Their Algorithmic Applications	p. 38
Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three	p. 43
Shortest paths between shortest paths and independent sets	p. 56
Faster Bit-Parrallel Algorithams for Unordered Pseudo-tree Matching and Tree Homeomorphism	p. 68
Dichotomy for coloring of dart graphs	p. 82
Worst case efficient single and multiple string matching in the RAM model	p. 90
The (2,1)-Total Labelimg Number of Outerplanar Graphs is at most ¿ + 2	p. 103
Upper and lower I/O Bounds for Pebbling r-pyramids	p. 107
Single Parameter FPT-Algorithms for Non-trivial Games
The Complexity Status of Problems Related to Sparsest Cuts	p. 125
On Approximation Complexity of Metric Dimension Problem	p. 136
Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates	p. 140
Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures	p. 154
Computing Role Assignments of Proper Interval Graphs in Polynomial Time	p. 167
Efficient Connectivity Testing of Hypercubic Networks with Faults	p. 181
Reductions of Matrices Associated with Nowhere-Zero flows	p. 192
Blocks of Hypergraphs: Applied to Hypergraphs and Outerplanarity	p. 201
Testing the Simultaneous Embeddability of Two Graphs Whose intersection Is a Biconnected Graph or a Tree	p. 212
Skip Lift: A Probabilistic Alternative to Red-Black Trees	p. 226
On a relationship between Completely Separating Systems and Antimagic labeling of Regular Graphs	p. 238
Parameterized Complexity of k-Anonymity: Hardness and Tractability	p. 242
On fast Enummeration of Pseudo Bicliques	p. 256
Efficient Chaining of seeds in Ordered Trees	p. 260
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs	p. 274
Recognition of Probe Ptolemaic Graphs(Ectended Abstract)	p. 286
Graphs of Separability at Most Two: Structural Characterizations and Their Consequences	p. 291
On Antimagic Labing for Generalized Web and Flower Graphs	p. 303
Chains-into-Bins processes	p. 314
Complexity of Locality Injective Homomorphism to the Theta Graphs	p. 326
Ranking and Drawing in Suberponential Time	p. 337
Efficient Reconstruction of RC-Equivalent strings	p. 349
Improved Points Approximation Algorithms Based on Simplical Thickness Data Structures	p. 363
The Cover Time of Cartesian Product Graphs	p. 377
Dictionary-Symbolwise Flexible Parsing	p. 390
Regular Language Constrained Sequence Alignment Eevisited	p. 404
Author index	p. 417
Table of Contents provided by Ingram. All Rights Reserved.