Graph-Theoretic Concepts in Computer Science: 21st International Workshop, WG '95, Aachen, Germany, June 20 - 22, 1995. ProceedingsManfred Nagl This book constitutes the refereed proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science, WG '95, held in Aachen, Germany, in June 1995. The WG workshop series contributes to integration in computer science by applying graph theoretical concepts in various areas as well as by taking up problems from practical applications and treating them theoretically. The book presents 30 carefully refereed revised papers selected from 52 submissions and reflects current activities in the field of computer science oriented graph theory, its computational aspects and its application. |
Contents
VCDimensions for Graphs | 1 |
Finding and Counting Small Induced Subgraphs Efficiently | 14 |
A Dynamic Algorithm for Line Graph Recognition | 37 |
Copyright | |
24 other sections not shown
Other editions - View all
Graph-Theoretic Concepts in Computer Science: 21st International Workshop ... Manfred Nagl No preview available - 2014 |
Common terms and phrases
2-component acyclic adjacent algorithm arbitrary assume Boolean bound C₁ calling schedule cell cellwork L-system chordal graph clique tree closure space cographs Computer Science consider contains cutwidth cycle database scheme defined Definition degenerated module denote diametral path graphs digraph directed graph dummy edge embedding exists faults forward closure G₁ genus given graph G graph rewriting h-extremal Hence hive graph homogeneously orderable hot-potato routing hyperarcs hyperedge hypergraph induced subgraph integer interval routing isomorphism L-system label Lemma Let G line graph linear maximal cliques maximum minimal modular decomposition multicast neighborhood neighbors node number of edges O(log O(n³ obtained optimal p-connected P₁ packet pair parallel partition coefficients path graphs permutation graphs planar graph polynomial problem processors Proof relationship type result routing schemes satisfying shortest path solution spanning tree step subset subtrees T₁ Theorem tree-decomposition treewidth unicast v₁ VC-dimension vertex vertex set