This book constitutes the revised selected papers of the 20th International Workshop on Combinatorial Algorithms, held in June/July 2009 in the castle of Hradec nad Moravicí, Czech Republic.
The 41 papers included in this volume together with 5 invited papers were carefully reviewed and selected from over 100 submissions. The topics dealt with are algorithms and data structures, applications, combinatorial enumeration, combinatorial optimization, complexity theory, computational biology, databases, decompositions and combinatorial designs, discrete and computational geometry, including graph drawing, and graph theory and combinatorics.
Author(s): Jack Edmonds (auth.), Jiří Fiala, Jan Kratochvíl, Mirka Miller (eds.)
Series: Lecture Notes in Computer Science 5874 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 480
Tags: Discrete Mathematics in Computer Science; Combinatorics; Algorithm Analysis and Problem Complexity; Mathematical Logic and Formal Languages; Coding and Information Theory; Symbolic and Algebraic Manipulation
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 -
