## Graph-Theoretic Concepts in Computer Science: 19th International Workshop, WG '93, Utrecht, The Netherlands, June 16 - 18, 1993. ProceedingsThis volume contains the proceedings of the 19th International Workshop on Graph-Theoretic Concepts in Computer Science, WG '93, held near Utrecht, The Netherlands, in 1993. The papers are grouped into parts on: hard problems on classes of graphs, structural graph theory, dynamic graph algorithms, structure-oriented graph algorithms, graph coloring, AT-free and chordal graphs, circuits and nets, graphs and interconnection networks, routing and shortest paths, and graph embedding and layout. The 35 revised papers were chosen from 92 submissions after a careful refereeing process. |

### What people are saying - Write a review

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

### Other editions - View all

Graph-Theoretic Concepts in Computer Science: 19th International Workshop ... Jan van Leeuwen No preview available - 2014 |

### Common terms and phrases

3-colourable 4-connected acyclic adjacent applied approximation algorithm AT-free graphs Boolean functions Cayley graph chordal graphs chromatic polynomial clique cograph color complete graph Computer Science consider constant construct contains Corollary corresponding cycle of length data structure defined degree denote directed graph disjoint dominating set ear decomposition elimination ordering embedding endpoints exists finite fully dynamic gossip graph G Graph Theory Hence hypercube hypergraph independent set induced subgraph insertions and deletions integer interval label Lemma Let G linear logn lower bound maximum genus neighbors NP-complete number of edges number of vertices O(logn OBDD obtained operations optimal pair perfect hash functions perfect matching planar graph processors Proof prove queries routing S-invariant sandwich problem sequence shortest path solution solved steps subgraph of G subset T-coloring Theorem topological order tree-decomposition treewidth unit disk graphs update upper bound vertex cover vertex set weight width

### Popular passages

Page 124 - Miller and J. Reif. Parallel tree contraction and its application. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages