Graph-Theoretic Concepts in Computer Science: 20th International Workshop, WG ’94 Herrsching, Germany, June 16–18, 1994 Proceedings

Hans L. Bodlaender, Joost Engelfriet (auth.), Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer (eds.)3540590714, 9783540590712

This volume presents the proceedings of the 20th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’94), held in Herrsching, Germany in June 1994.
The volume contains 32 thoroughly revised papers selected from 66 submissions and provides an up-to-date snapshot of the research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems.

---

Table of contents :
Domino treewidth….Pages 1-13
A lower bound for treewidth and its consequences….Pages 14-25
Tree-width and path-width of comparability graphs of interval orders….Pages 26-37
A declarative approach to graph based modeling….Pages 38-50
Multilevel graph grammars….Pages 51-64
The algorithmic use of hypertree structure and maximum neighbourhood orderings….Pages 65-80
On domination elimination orderings and domination graphs….Pages 81-92
Complexity of graph covering problems….Pages 93-105
Dominoes….Pages 106-120
GLB-closures in directed acyclic graphs and their applications….Pages 121-129
Minimum vertex cover, distributed decision-making, and communication complexity….Pages 130-139
Cartesian products of graphs as spanning subgraphs of de Bruijn graphs….Pages 140-150
Specification of graph translators with triple graph grammars….Pages 151-163
Using programmed graph rewriting for the formal specification of a configuration management system….Pages 164-179
Exponential time analysis of confluent and boundary eNCE graph languages….Pages 180-192
Time-optimal tree computations on sparse meshes….Pages 193-205
Prefix graphs and their applications….Pages 206-218
The complexity of broadcasting in planar and decomposable graphs….Pages 219-231
The maximal f -dependent set problem for planar graphs is in NC….Pages 232-241
On-line convex planarity testing….Pages 242-255
Book embeddings and crossing numbers….Pages 256-268
Measuring the distance to series-parallelity by path expressions….Pages 269-281
Labelled trees and pairs of input-output permutations in priority queues….Pages 282-291
Rankings of graphs….Pages 292-304
Bypass strong V-structures and find an isomorphic labelled subgraph in linear time….Pages 305-318
Efficient algorithms for a mixed k-partition problem of graphs without specifying bases….Pages 319-330
Fugitive-search games on graphs and related parameters….Pages 331-342
New approximation results on graph matching and related problems….Pages 343-358
New lower bounds and hierarchy results for restricted branching programs….Pages 359-370
On-line algorithms for satisfiability problems with uncertainty….Pages 371-386
NC algorithms for antidirected hamiltonian paths and cycles in tournaments….Pages 387-394
Directed path graph isomorphism….Pages 395-406