Graph-Theoretic Concepts in Computer Science: 30th International Workshop, Wg 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers

ISBN-13: 9783540241324 / Angielski / Miękka / 2004 / 404 str.

Juraj Hromkovic; Manfred Nagl; Bernhard Westfechtel

Opis

This book constitutes the thoroughly refereed post-proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, held in Bad Honnef, Germany in June 2004.

The 31 revised full papers presented together with 2 invited papers were carefully selected from 66 submissions during two rounds of reviewing and improvement. The papers are organized in topical sections on graph algorithms: trees; graph algorithms: recognition and decomposition; graph algorithms: various problems; optimization and approximation algorithms; parameterized complexity and exponential algorithms; counting, combinatorics, and optimization; applications in bioinformatics and graph drawing; and graph classes and NP-hard problems.

Spis treści

Invited Papers.- Lexicographic Breadth First Search – A Survey.- Wireless Networking: Graph Theory Unplugged.- Graph Algorithms: Trees.- Constant Time Generation of Trees with Specified Diameter.- Treelike Comparability Graphs: Characterization, Recognition, and Applications.- Elegant Distance Constrained Labelings of Trees.- Collective Tree Spanners and Routing in AT-free Related Graphs.- Graph Algorithms: Recognition and Decomposition.- On the Maximum Cardinality Search Lower Bound for Treewidth.- Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs.- Recognizing HHD-free and Welsh-Powell Opposition Graphs.- Bimodular Decomposition of Bipartite Graphs.- Coloring a Graph Using Split Decomposition.- Graph Algorithms: Various Problems.- Decremental Clique Problem.- A Symbolic Approach to the All-Pairs Shortest-Paths Problem.- Minimal de Bruijn Sequence in a Language with Forbidden Substrings.- A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic .- Optimization and Approximation Algorithms.- The Computational Complexity of the Minimum Weight Processor Assignment Problem.- A Stochastic Location Problem with Applications to Tele-diagnostic.- A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs.- Tolerance Based Algorithms for the ATSP.- Parameterized Complexity and Exponential Algorithms.- Finding k Disjoint Triangles in an Arbitrary Graph.- Exact (Exponential) Algorithms for the Dominating Set Problem.- Linear Kernels in Linear Time, or How to Save k Colors in O(n 2) Steps.- Counting, Combinatorics, and Optimization.- Planar Graphs, via Well-Orderly Maps and Trees.- Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs.- Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters.- Applications (Biology, Graph Drawing).- Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs.- Octagonal Drawings of Plane Graphs with Prescribed Face Areas.- Crossing Reduction in Circular Layouts.- Graph Classes and NP Hardness.- Characterization and Recognition of Generalized Clique-Helly Graphs.- Edge-Connectivity Augmentation and Network Matrices.- Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size.- The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small.- Core Stability of Minimum Coloring Games.

O autorze

Prof. Dr. Juraj Hromkovic war 1997 - 2003 Professor für Algorithmen und Komplexität an der RWTH Aachen. Seit Januar 2004 ist er Professor für Informatik an der ETH Zürich. Seit 2010 ist er Mitglied der Academia Europaea. Prof. Dr.-Ing. habil. Manfred Nagl ist Inhaber des Lehrstuhls Informatik III an der Rheinisch-Westfälischen Technischen Hochschule Aachen.