Graph-Theoretic Concepts in Computer Science

17th International Workshop WG '91, Fischbachau, Germany, June 17-19, 1991. Proceedings
1992
ISBN: 978-3-540-55121-8
Verlag: Springer Berlin Heidelberg

Buch, Englisch, Band 570, 256 Seiten, Paperback, Format (B × H): 155 mm x 235 mm, Gewicht: 411 g

Reihe: Lecture Notes in Computer Science

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.

Zielgruppe

Research

Autoren/Hrsg.

Berghammer, Rudolf

Schmidt, Gunther

Fachgebiete

• Mathematik | Informatik EDV | Informatik Programmierung | Softwareentwicklung Programmierung: Methoden und Allgemeines
• Mathematik | Informatik EDV | Informatik Informatik Mathematik für Informatiker
• Mathematik | Informatik Mathematik Algebra Elementare Algebra
• Mathematik | Informatik EDV | Informatik Technische Informatik Hochleistungsrechnen, Supercomputer
• Mathematik | Informatik EDV | Informatik Daten / Datenbanken Zeichen- und Zahlendarstellungen
• Mathematik | Informatik EDV | Informatik Informatik Logik, formale Sprachen, Automaten
• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Technische Wissenschaften Elektronik | Nachrichtentechnik Elektronik Mikroprozessoren

Inhaltsverzeichnis

Approximating treewidth, pathwidth, and minimum elimination tree height.- Monadic second-order evaluations on tree-decomposable graphs.- Optimal embedding of complete binary trees into lines and grids.- Graph rewriting systems and their application to network reliability analysis.- Nondeterministic control structures for graph rewriting systems.- A language for generic graph-transformations.- Attributed elementary programmed graph grammars.- The complexity of approximating the class Steiner tree problem.- On complexity of some chain and antichain partition problems.- Tight bounds for the rectangular art gallery problem.- Voronoi diagrams of moving points in the plane.- Using maximal independent sets to solve problems in parallel.- Fast parallel algorithms for coloring random graphs.- Optimal vertex ordering of a graph and its application to symmetry detection.- Edge separators for graphs of bounded genus with applications.- Line digraph iterations and the spread concept—with application to graph theory, fault tolerance, and routing.- A generalized encryption scheme based on random graphs.- Dynamic algorithms for shortest paths in planar graphs.- Complete problems for logspace involving lexicographic first paths in graphs.- A new upper bound on the complexity of the all pairs shortest path problem.- On the crossing number of the hypercube and the cube connected cycles.- Logic arrays for interval indicator functions.- On the broadcast time of the butterfly network.- On disjoint cycles.- Short disjoint cycles in cubic bridgeless graphs.