Combinatorial Algorithms: 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers

Front Matter....Pages -
Branching Systems....Pages 1-1
Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology....Pages 2-10
Succinct Representations of Trees....Pages 11-18
 K t Minors in Large t -Connected Graphs....Pages 19-19
Intractability in Graph Drawing and Geometry: FPT Approaches....Pages 20-23
Evaluation of Recoverable-Robust Timetables on Tree Networks....Pages 24-35
Weighted LCS....Pages 36-47
Integrality Properties of Certain Special Balanceable Families....Pages 48-59
Forbidden Subgraph Colorings and the Oriented Chromatic Number....Pages 60-71
Polynomial Kernels for 3-Leaf Power Graph Modification Problems....Pages 72-82
Approximating the Max Edge-Coloring Problem....Pages 83-94
Three Complexity Results on Coloring P k -Free Graphs....Pages 95-104
Fully Decomposable Split Graphs....Pages 105-112
Feedback Vertex Set on Graphs of Low Cliquewidth....Pages 113-124
Note on Decomposition of K n,n into (0, j )-prisms....Pages 125-133
Edge-Simple Circuits through 10 Ordered Vertices in Square Grids....Pages 134-145
Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O ( n ) Breadth-First Search....Pages 146-157
LPF Computation Revisited....Pages 158-169
Limiting Distribution for Distances in k -Trees....Pages 170-182
Gray Code Compression....Pages 183-193
Embedded Trees and the Support of the ISE....Pages 194-205
Combinatorial Models for Cooperation Networks....Pages 206-217
Polar Permutation Graphs....Pages 218-229
A New Algorithm for Efficient Pattern Matching with Swaps....Pages 230-241
The Height and Range of Watermelons without Wall....Pages 242-253
Fast Convolutions and Their Applications in Approximate String Matching....Pages 254-265
Better Polynomial Algorithms on Graphs of Bounded Rank-Width....Pages 266-277
Minimax Trees in Linear Time with Applications....Pages 278-288
Planar Biconnectivity Augmentation with Fixed Embedding....Pages 289-300
Trivially-Perfect Width....Pages 301-311
Lightweight Parameterized Suffix Array Construction....Pages 312-323
On the Crossing Numbers of Cartesian Products of Stars and Graphs on Five Vertices....Pages 324-333
Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees....Pages 334-344
On the Maximal Number of Cubic Subwords in a String....Pages 345-355
Solution of Peter Winkler’s Pizza Problem....Pages 356-367
An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs....Pages 368-379
Simpler Parameterized Algorithm for OCT....Pages 380-384
Bipartite Graphs of Large Clique-Width....Pages 385-395
Kernel in Oriented Circulant Graphs....Pages 396-407
Randomized Postoptimization of Covering Arrays....Pages 408-419
New Word-Based Adaptive Dense Compressors....Pages 420-431
Rainbow Connection in Graphs with Minimum Degree Three....Pages 432-437
The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree....Pages 438-449
Computability of Width of Submodular Partition Functions....Pages 450-459
The Guarding Problem – Complexity and Approximation....Pages 460-470
Antibandwidth of d-Dimensional Meshes....Pages 471-477
Back Matter....Pages -