Graph-Theoretic Concepts in Computer Science: 18th International Workshop, WG ’92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings

Andreas Brandstädt (auth.), Ernst W. Mayr (eds.)3540564020, 9783540564027

The 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’92) was held in Wiesbaden-Naurod, Germany, June 18-20, 1992. Itwas organized by the Department of Computer Science, Johann Wolfgang Goethe University, Frankfurt am Main. Contributions with original results inthe study and application of graph-theoretic concepts in various fields of computer science were solicited, and 72 papers were submitted and reviewed, from which 29 were selected for presentation at the workshop. The workshop was attended by 61 scientists from 16 countries. All 29 papers in the volume have undergone careful revision after the meeting, based on the discussions and comments from the audience and the referees. The volume is divided into parts on restricted graph classes, scheduling and related problems, parallel anbd distributed algorithms, combinatorial graph problems, graph decomposition, graph grammars and geometry, and modelling by graphs.

---

Table of contents :
On improved time bounds for permutation graph problems….Pages 1-10
A simple test for interval graphs….Pages 11-16
Tolerance graphs and orders….Pages 17-26
On scheduling problems restricted to interval orders….Pages 27-36
Scheduling with incompatible jobs….Pages 37-49
Generalized coloring for tree-like graphs….Pages 50-59
Optimal (parallel) algorithms for the all-to-all vertices distance problem for certain graph classes….Pages 60-69
Topology of parallel networks and computational complexity (extended abstract)….Pages 70-77
Parallel triangulation of nonconvex polytopes….Pages 78-89
Kayles on special classes of graphs — An application of Sprague-Grundy theory….Pages 90-102
A linear time algorithm for isomorphism of graphs of bounded average genus….Pages 103-113
Improved algorithms for routing on two-dimensional grids….Pages 114-122
Minimum rectilinear steiner trees for intervals on two parallel lines….Pages 123-134
A new characterization of tree medians with applications to distributed algorithms….Pages 135-144
The 3-edge-components and a structural description of all 3-edge-cuts in a graph….Pages 145-157
On assembly of four-connected graphs….Pages 158-169
On the homogeneous decomposition of graphs….Pages 170-183
Embeddings in recursive combinatorial networks….Pages 184-204
On shortcutting digraphs….Pages 205-211
An efficient algorithm to recognize prime undirected graphs….Pages 212-224
On the complexity of partial order properties….Pages 225-235
Probabilistic graph grammars….Pages 236-247
Single vs. double pushout derivations of graphs….Pages 248-262
Hexagonal grid drawings….Pages 263-276
Graph algorithms = iteration + data structures?….Pages 277-292
Petri nets, hypergraphs and conflicts (preliminary version)….Pages 293-309
Analysis and manipulation of Boolean functions in terms of decision graphs….Pages 310-320
The expressiveness of silence: Tight bounds for synchronous communication of information using bits and silence….Pages 321-332
The power and the limitations of local computations on graphs….Pages 333-345