## Graph-Theoretic Concepts in Computer Science: 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings, Volume 20This 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 research performed in the field. The topics addressed are graph grammars, treewidth, special graph classes, algorithms on graphs, broadcasting and architecture, planar graphs and related problems, and special graph problems. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

25 | |

36 | |

Multilevel Graph Grammars | 51 |

The Algorithmic Use of Hypertree Structure and Maximum | 65 |

On Domination Elimination Orderings and Domination Graphs | 81 |

Complexity of Graph Covering Problems | 93 |

Dominoes | 106 |

GLBClosures in Directed Acyclic Graphs and Their Applications | 121 |

Minimum Vertex Cover Distributed DecisionMaking | 130 |

Cartesian Products of Graphs as Spanning Subgraphs of De Bruijn | 140 |

Using Programmed Graph Rewriting for the Formal Specification of | 164 |

411 | |

### Other editions - View all

### Common terms and phrases

ADHP adjacent algorithm application assume biconnected graph binary tree bipartite graphs Boolean branching programs broadcast chordal graphs chordless cycle class of graphs color complete graph complexity component Computer Science connected enumeration construction contains corresponding cycle decomposition defined Definition degree denote domino dually chordal graphs duplicated expression edge elimination ordering embedding eNCE graph grammars encoding exists function given graph G graph rewriting Horn formula hyperedge hypergraph induced subgraph input integer interval graph isomorphism label Lemma Let G line graph linear lower bound matching maximal cliques maximum morphism multilevel graph nonterminal nodes NP-complete number of vertices O(logn obtain ordered tree pair parallel partition pathwidth planar graph polynomial prefix graph problem without bases Proc processors production Proof r-dominating recursively result search number searchers sequence simplicial solved specification st-dag subdag subset Theorem treewidth triple variables vertex ranking weight