Graph-Theoretic Concepts in Computer Science: 17th International Workshop WG '91, Fischbachau, Germany, June 17-19, 1991. ProceedingsSpringer Science & Business Media, 29.01.1992 - 252 Seiten This volume contains contributions to the 17th International workshop on Graph-Theoretic Concepts in Computer Science (WG '91) held in Southern Bavaria in June 1991. These annual workshops are designed to bring together researchers using graph-theoretic methods to discuss new developments relating to or emerging from a diversity of application fields. The topics covered in this volume include: tree-related problems, graph grammarsand rewriting, complexity, computational geometry, parallel algorithms, vertex orderings, path-oriented algorithms, applications to VLSI, and disjoint cycle problems. |
Inhalt
Approximating Treewidth Pathwidth and Minimum Elimination Tree Height | 1 |
Monadic SecondOrder Evaluations on TreeDecomposable Graphs | 13 |
Optimal Embedding of Complete Binary Trees into Lines and Grids | 25 |
Graph Rewriting Systems and their Application to Network Reliability Analysis | 36 |
Nondeterministic Control Structures for Graph Rewriting Systems | 48 |
A Language for Generic GraphTransformations | 63 |
Attributed Elementary Programmed Graph Grammars | 75 |
The Complexity of Approximating the Class Steiner Tree Problem | 85 |
EDGE SEPARATORS FOR GRAPHS OF BOUNDED GENUS WITH APPLICATIONS | 159 |
Line Digraph Iterations and the Spread Conceptwith Application to Graph Theory Fault Tolerance and Routing | 169 |
A Generalized Encryption Scheme Based on Random Graphs | 180 |
Dynamic Algorithms for Shortest Paths in Planar Graphs | 187 |
COMPLETE PROBLEMS FOR LOGSPACE INVOLVING LEXICOGRAPHIC FIRST PATHS IN GRAPHS | 198 |
A New Upper Bound on the Complexity of the All Pairs Shortest Path Problem | 209 |
ON THE CROSSING NUMBER OF THE HYPERCUBE AND THE CUBE CONNECTED CYCLES | 214 |
LOGIC ARRAYS FOR INTERVAL INDICATOR FUNCTIONS | 219 |
On Complexity of Some Chain and Antichain Partition Problems | 97 |
TIGHT BOUNDS FOR THE RECTANGULAR ART GALLERY PROBLEM | 105 |
Voronoi Diagrams of Moving Points in the Plane | 113 |
in Parallel | 126 |
Fast Parallel Algorithms for Coloring Random Graphs | 135 |
Optimal Vertex Ordering of a Graph and its Application to Symmetry Detection | 148 |
On the broadcast time of the Butterfly network | 226 |
ON DISJOINT CYCLES | 230 |
Short disjoint cycles in cubic bridgeless graphs | 239 |
List of Participants | 250 |
List of Authors | |
Häufige Begriffe und Wortgruppen
applications approximation algorithm boundary vertices called CLASS STEINER TREE clique complete binary tree Computer Science connected constant contains critical pair data structure defined Definition deletion denote DT(S E₁ elementary programmed graph elimination tree embedding encryption exists feedback vertex set Figure finite function given graph G graph productions graph rewriting independent set Informatik integers isomorphism label Lemma length line digraph line digraph iterations linear lower bound m-edges mapping maximal maximum MDNF minimal minimum nondeterministic NP-complete NP-hard number of vertices O(log object base instance optimal vertex ordering ordered set parallel algorithm partition pathwidth planar graphs points polynomial preprocessing problem Proc Proceedings processors programmed graph grammars Proof prove random graphs reduction resp result sequence set cover shortest path shortest path problem spanning tree Steiner nodes subgraph subset Theorem Theory topological events tree-decomposition treewidth upper bound V₁ Voronoi diagram W₁