Graph-Theoretic Concepts in Computer Science计算机科学中的图论概念

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.

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 CL
Optimization and Approximation Algorithms
The Computational Complexity of the Mininmum 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(n2) Steps
Counting, Combinatorics, and Optimization
Planar Graphs, via Well-Orderly Maps and Trees
……
Applications (Biology,Graph Drawing)
Graph Classes and NP Hardness
Author Index