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

Front Matter....Pages -
Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes....Pages 1-9
On the Maximal Sum of Exponents of Runsin a String....Pages 10-19
Path-Based Supports for Hypergraphs....Pages 20-33
On Improved Exact Algorithms for L (2,1)-Labeling of Graphs....Pages 34-37
Thread Graphs, Linear Rank-Width and Their Algorithmic Applications....Pages 38-42
Minimum Number of Holes in Unavoidable Sets of Partial Words of Size Three....Pages 43-55
Shortest Paths between Shortest Paths and Independent Sets....Pages 56-67
Faster Bit-Parallel Algorithms for Unordered Pseudo-tree Matching and Tree Homeomorphism....Pages 68-81
Dichotomy for Coloring of Dart Graphs....Pages 82-89
Worst Case Efficient Single and Multiple String Matching in the RAM Model....Pages 90-102
The (2,1)-Total Labeling Number of Outerplanar Graphs Is at Most Δ + 2....Pages 103-106
Upper and Lower I/O Bounds for Pebbling r -Pyramids....Pages 107-120
Single Parameter FPT-Algorithms for Non-trivial Games....Pages 121-124
The Complexity Status of Problems Related to Sparsest Cuts....Pages 125-135
On Approximation Complexity of Metric Dimension Problem....Pages 136-139
Collision-Free Routing in Sink-Centric Sensor Networks with Coarse-Grain Coordinates....Pages 140-153
Complexity of Most Vital Nodes for Independent Set in Graphs Related to Tree Structures....Pages 154-166
Computing Role Assignments of Proper Interval Graphs in Polynomial Time....Pages 167-180
Efficient Connectivity Testing of Hypercubic Networks with Faults....Pages 181-191
Reductions of Matrices Associated with Nowhere-Zero Flows....Pages 192-200
Blocks of Hypergraphs....Pages 201-211
Testing the Simultaneous Embeddability of Two Graphs Whose Intersection Is a Biconnected Graph or a Tree....Pages 212-225
Skip Lift: A Probabilistic Alternative to Red-Black Trees....Pages 226-237
On a Relationship between Completely Separating Systems and Antimagic Labeling of Regular Graphs....Pages 238-241
Parameterized Complexity of k -Anonymity: Hardness and Tractability....Pages 242-255
On Fast Enumeration of Pseudo Bicliques....Pages 256-259
Efficient Chaining of Seeds in Ordered Trees....Pages 260-273
On the Computational Complexity of Degenerate Unit Distance Representations of Graphs....Pages 274-285
Recognition of Probe Ptolemaic Graphs....Pages 286-290
Graphs of Separability at Most Two: Structural Characterizations and Their Consequences....Pages 291-302
On Antimagic Labeling for Generalized Web and Flower Graphs....Pages 303-313
Chains-into-Bins Processes....Pages 314-325
Complexity of Locally Injective Homomorphism to the Theta Graphs....Pages 326-336
Ranking and Drawing in Subexponential Time....Pages 337-348
Efficient Reconstruction of RC-Equivalent Strings....Pages 349-362
Improved Points Approximation Algorithms Based on Simplicial Thickness Data Structures....Pages 363-376
The Cover Time of Cartesian Product Graphs....Pages 377-389
Dictionary-Symbolwise Flexible Parsing....Pages 390-403
Regular Language Constrained Sequence Alignment Revisited....Pages 404-415
Back Matter....Pages -