Combinatorial Algorithms : 20th International Workshop, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28--July 2, 2009, Revised Selected Papers / edited by Jiri Fiala, Jan Kratochvil, Mirka Miller.

Format:

Book

Contributor:

Fiala, Jiří, 1973- editor.

Kratochvíl, Jan, editor.

Miller, Mirka, 1949- editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 5874.

Theoretical Computer Science and General Issues ; 5874

Language:

English

Subjects (All):

Computer science--Mathematics.

Computer science.

Combinatorial analysis.

Algorithms.

Logic, Symbolic and mathematical.

Coding theory.

Information theory.

Discrete Mathematics in Computer Science.

Combinatorics.

Algorithm Analysis and Problem Complexity.

Mathematical Logic and Formal Languages.

Coding and Information Theory.

Symbolic and Algebraic Manipulation.

Local Subjects:

Discrete Mathematics in Computer Science.

Combinatorics.

Algorithm Analysis and Problem Complexity.

Mathematical Logic and Formal Languages.

Coding and Information Theory.

Symbolic and Algebraic Manipulation.

Physical Description:

1 online resource (XII, 480 pages).

Edition:

First edition 2009.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2009.

System Details:

text file PDF

Summary:

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.

Contents:

Invited Talks

Branching Systems

Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology

Succinct Representations of Trees

Kt Minors in Large t-Connected Graphs

Intractability in Graph Drawing and Geometry: FPT Approaches

Contributed Talks

Evaluation of Recoverable-Robust Timetables on Tree Networks

Weighted LCS

Integrality Properties of Certain Special Balanceable Families

Forbidden Subgraph Colorings and the Oriented Chromatic Number

Polynomial Kernels for 3-Leaf Power Graph Modification Problems

Approximating the Max Edge-Coloring Problem

Three Complexity Results on Coloring P k -Free Graphs

Fully Decomposable Split Graphs

Feedback Vertex Set on Graphs of Low Cliquewidth

Note on Decomposition of K n,n into (0,j)-prisms

Edge-Simple Circuits through 10 Ordered Vertices in Square Grids

Efficient Neighborhood Encoding for Interval Graphs and Permutation Graphs and O(n) Breadth-First Search

LPF Computation Revisited

Limiting Distribution for Distances in k-Trees

Gray Code Compression

Embedded Trees and the Support of the ISE

Combinatorial Models for Cooperation Networks

Polar Permutation Graphs

A New Algorithm for Efficient Pattern Matching with Swaps

The Height and Range of Watermelons without Wall

Fast Convolutions and Their Applications in Approximate String Matching

Better Polynomial Algorithms on Graphs of Bounded Rank-Width

Minimax Trees in Linear Time with Applications

Planar Biconnectivity Augmentation with Fixed Embedding

Trivially-Perfect Width

Lightweight Parameterized Suffix Array Construction

On the Crossing Numbers of Cartesian Products of Stars and Graphs on Five Vertices

Factorizations of Complete Graphs into Spanning Trees with All Possible Maximum Degrees

On the Maximal Number of Cubic Subwords in a String

Solution of Peter Winkler's Pizza Problem

An O(n)-Time Algorithm for the Paired-Domination Problem on Permutation Graphs

Simpler Parameterized Algorithm for OCT

Bipartite Graphs of Large Clique-Width

Kernel in Oriented Circulant Graphs

Randomized Postoptimization of Covering Arrays

New Word-Based Adaptive Dense Compressors

Rainbow Connection in Graphs with Minimum Degree Three

The Complexity of Almost Perfect Matchings in Uniform Hypergraphs with High Codegree

Computability of Width of Submodular Partition Functions

The Guarding Problem - Complexity and Approximation

Antibandwidth of d-Dimensional Meshes.

Other Format:

Printed edition:

ISBN:

978-3-642-10217-2

9783642102172

Access Restriction:

Restricted for use by site license.