During its 30-year existence, the International Workshop on Graph-Theoretic Concepts in Computer Science has become a distinguished and high-quality computer science event. The workshop aims at uniting theory and practice by demonstrating how graph-theoretic concepts can successfully be applied to v- ious areas of computer science and by exposing new theories emerging from applications. In this way, WG provides a common ground for the exchange of information among people dealing with several graph problems and working in various disciplines. Thereby, the workshop contributes to forming an interdis- plinary research community. The original idea of the Workshop on Graph-Theoretic Concepts in C- puter Science was ingenuity in all theoretical aspects and applications of graph concepts, wherever applied. Within the last ten years, the development has strengthened in particular the topic of structural graph properties in relation to computational complexity. This workshop has become pivotal for the c- munity interested in these areas.An aimspeci?c to the 30thWG was to support the central role of WG in both of the prementioned areas on the one hand and on the other hand to promote its originally broader scope. The 30th WG was held at the Physikzentrum Bad Honnef, which serves as the main meeting point of the German Physical Society. It o?ers a secluded setting for research conferences, seminars, and workshops, and has proved to be especiallystimulatingforfruitful discussions.Talksweregiveninthenewlecture hall with a modern double rear projection, interactive electronic board, and full video conferencing equipment.
Author(s): Derek G. Corneil (auth.), Juraj Hromkovič, Manfred Nagl, Bernhard Westfechtel (eds.)
Series: Lecture Notes in Computer Science 3353
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 404
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Numeric Computing; Data Structures; Computer Graphics; Algorithms
Front Matter....Pages -
Lexicographic Breadth First Search – A Survey....Pages 1-19
Wireless Networking: Graph Theory Unplugged....Pages 20-32
Constant Time Generation of Trees with Specified Diameter....Pages 33-45
Treelike Comparability Graphs: Characterization, Recognition, and Applications....Pages 46-57
Elegant Distance Constrained Labelings of Trees....Pages 58-67
Collective Tree Spanners and Routing in AT-free Related Graphs....Pages 68-80
On the Maximum Cardinality Search Lower Bound for Treewidth....Pages 81-92
Fully-Dynamic Recognition Algorithm and Certificate for Directed Cographs....Pages 93-104
Recognizing HHD-free and Welsh-Powell Opposition Graphs....Pages 105-116
Bimodular Decomposition of Bipartite Graphs....Pages 117-128
Coloring a Graph Using Split Decomposition....Pages 129-141
Decremental Clique Problem....Pages 142-153
A Symbolic Approach to the All-Pairs Shortest-Paths Problem....Pages 154-167
Minimal de Bruijn Sequence in a Language with Forbidden Substrings....Pages 168-176
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic $\mathcal{EL}$ ....Pages 177-188
The Computational Complexity of the Minimum Weight Processor Assignment Problem....Pages 189-200
A Stochastic Location Problem with Applications to Tele-diagnostic....Pages 201-213
A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs....Pages 214-221
Tolerance Based Algorithms for the ATSP....Pages 222-234
Finding k Disjoint Triangles in an Arbitrary Graph....Pages 235-244
Exact (Exponential) Algorithms for the Dominating Set Problem....Pages 245-256
Linear Kernels in Linear Time, or How to Save k Colors in O ( n 2 ) Steps....Pages 257-269
Planar Graphs, via Well-Orderly Maps and Trees....Pages 270-284
Efficient Computation of the Lovász Theta Function for a Class of Circulant Graphs....Pages 285-295
Unhooking Circulant Graphs: A Combinatorial Method for Counting Spanning Trees and Other Parameters....Pages 296-307
Computing Bounded-Degree Phylogenetic Roots of Disconnected Graphs....Pages 308-319
Octagonal Drawings of Plane Graphs with Prescribed Face Areas....Pages 320-331
Crossing Reduction in Circular Layouts....Pages 332-343
Characterization and Recognition of Generalized Clique-Helly Graphs....Pages 344-354
Edge-Connectivity Augmentation and Network Matrices....Pages 355-364
Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size....Pages 365-376
The Hypocoloring Problem: Complexity and Approximability Results when the Chromatic Number Is Small....Pages 377-388
Core Stability of Minimum Coloring Games....Pages 389-401
Back Matter....Pages -
