+612 9045 4394
Graph-Theoretic Concepts in Computer Science : 17th International Workshop Wg '91, Fischbachau, Germany, June 17-19, 1991. Proceedings - Gunther Schmidt

Graph-Theoretic Concepts in Computer Science

17th International Workshop Wg '91, Fischbachau, Germany, June 17-19, 1991. Proceedings

By: Gunther Schmidt (Editor), Rudolf Berghammer (Editor)

Paperback Published: 29th January 1992
ISBN: 9783540551218
Number Of Pages: 256

Share This Book:


or 4 easy payments of $31.26 with Learn more
Ships in 5 to 9 business days

This volume contains contributions to the 17th Internationalworkshop on Graph-Theoretic Concepts in Computer Science(WG '91) held in Southern Bavaria in June 1991. These annualworkshops are designed to bring together researchers usinggraph-theoretic methods to discuss new developments relatingto or emerging from a diversity of application fields.The topics covered in this volume include: tree-relatedproblems, graph grammarsand rewriting, complexity,computational geometry, parallel algorithms, vertexorderings, path-oriented algorithms, applications to VLSI,and disjoint cycle problems.

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.

ISBN: 9783540551218
ISBN-10: 3540551212
Series: Lecture Notes in Engineering
Audience: General
Format: Paperback
Language: English
Number Of Pages: 256
Published: 29th January 1992
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 1.45
Weight (kg): 0.39