Graph-Theoretic Concepts in Computer Science: 20th International Workshop. WG '94, Herrsching, Germany, June 16 - 18, 1994. Proceedings
Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer
Springer, Apr 26, 1995 - Computers - 414 pages
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 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.
85 pages matching given in this book
Results 1-3 of 85
What people are saying - Write a review
We haven't found any reviews in the usual places.
A Lower Bound for Treewidth and Its Consequences
19 other sections not shown
ADHP adjacent assume biconnected graph binary tree Boolean branching programs broadcast chordal graphs chordless cycle class of graphs clique color complete graph complexity components Computer Science connected enumeration construction contains convex drawing convex planar Corollary corresponding crossing number cycle decomposition defined Definition degree denote duplicated expression eNCE graph grammars encoding exists factoring function given graph G graph isomorphism graph rewriting Horn formula hyperedge hypergraph induced subgraph inert fugitive Informatik input integer isomorphism layered graph Lemma Let G linear lower bound matching maximal maximum minimal node reduction nonterminal nonterminal nodes NP-complete number of vertices obtain optimal ordered tree pair path graphs permutation planar graph polynomial prefix graph problem without bases Proc processors productions Proof recursively result root search number searchers sequence solved st-dag step strong V-structures subdag subexpression subset Theorem tournament tree-decomposition treewidth triconnected triple upper bound variables vertex ranking weight width