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

Graph-Theoretic Concepts in Computer Science 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings / edited by Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer.

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 re...

Full description

Saved in:
Bibliographic Details
Corporate Author: SpringerLink (Online service)
Other Authors: Mayr, Ernst W. (Editor), Schmidt, Gunther (Editor), Tinhofer, Gottfried (Editor)
Format: eBook
Language:English
Published: Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 1995.
Edition:1st ed. 1995.
Series:Lecture Notes in Computer Science, 903
Springer eBook Collection.
Subjects:
Computers.
Discrete mathematics.
Algorithms.
Combinatorics.
Computer logic.
Electronic resources (E-books)
Online Access:Click to view e-book
Holy Cross Note:Loaded electronically.
Electronic access restricted to members of the Holy Cross Community.
Table of Contents:
  • Domino treewidth
  • A lower bound for treewidth and its consequences
  • Tree-width and path-width of comparability graphs of interval orders
  • A declarative approach to graph based modeling
  • Multilevel graph grammars
  • The algorithmic use of hypertree structure and maximum neighbourhood orderings
  • On domination elimination orderings and domination graphs
  • Complexity of graph covering problems
  • Dominoes
  • GLB-closures in directed acyclic graphs and their applications
  • Minimum vertex cover, distributed decision-making, and communication complexity
  • Cartesian products of graphs as spanning subgraphs of de Bruijn graphs
  • Specification of graph translators with triple graph grammars
  • Using programmed graph rewriting for the formal specification of a configuration management system
  • Exponential time analysis of confluent and boundary eNCE graph languages
  • Time-optimal tree computations on sparse meshes
  • Prefix graphs and their applications
  • The complexity of broadcasting in planar and decomposable graphs
  • The maximal f-dependent set problem for planar graphs is in NC
  • On-line convex planarity testing
  • Book embeddings and crossing numbers
  • Measuring the distance to series-parallelity by path expressions
  • Labelled trees and pairs of input-output permutations in priority queues
  • Rankings of graphs
  • Bypass strong V-structures and find an isomorphic labelled subgraph in linear time
  • Efficient algorithms for a mixed k-partition problem of graphs without specifying bases
  • Fugitive-search games on graphs and related parameters
  • New approximation results on graph matching and related problems
  • New lower bounds and hierarchy results for restricted branching programs
  • On-line algorithms for satisfiability problems with uncertainty
  • NC algorithms for antidirected hamiltonian paths and cycles in tournaments
  • Directed path graph isomorphism.

Similar Items