Graph-Theoretic Concepts in Computer Science: 21st International Workshop, WG ’95 Aachen, Germany, June 20–22, 1995 Proceedings

Evangelos Kranakis, Danny Krizanc (auth.), Manfred Nagl (eds.)3540606181, 9783540606185

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.

---

Table of contents :
VC-dimensions for graphs (extended abstract)….Pages 1-13
Finding and counting small induced subgraphs efficiently….Pages 14-23
On the isomorphism of graphs with few P 4 s….Pages 24-36
A dynamic algorithm for line graph recognition….Pages 37-48
Incremental hive graph….Pages 49-61
Planarization of graphs embedded on surfaces….Pages 62-72
Complexity and approximability of certain bicriteria location problems….Pages 73-87
On termination of graph rewriting….Pages 88-100
A uniform approach to graph rewriting: The pullback approach….Pages 101-115
Visualizing two- and three-dimensional models of meristematic growth….Pages 116-130
Graph-theoretical methods to construct entity-relationship databases….Pages 131-145
An approximation algorithm for 3-Colourability….Pages 146-151
The malleability of TSP 2Opt ….Pages 152-166
Non-oblivious local search for graph and hypergraph coloring problems….Pages 167-180
On Interval Routing Schemes and treewidth….Pages 181-196
Highly fault-tolerant routings and diameter vulnerability for generalized hypercube graphs….Pages 197-208
Hot-potato routing on multi-dimensional tori….Pages 209-221
On devising Boolean Routing schemes….Pages 222-236
Toward a general theory of unicast-based multicast communication….Pages 237-251
Optimal cutwidths and bisection widths of 2- and 3-dimensional meshes….Pages 252-264
Searching for faulty leaves in binary trees….Pages 265-274
NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems….Pages 275-289
Efficient parallel modular decomposition (extended abstract)….Pages 290-302
Modular decomposition of hypergraphs….Pages 303-317
Partition coefficients of acyclic graphs….Pages 318-332
Sub-cubic cost algorithms for the all pairs shortest path problem….Pages 333-343
Diametral path graphs….Pages 344-357
Chordal graphs and their clique graphs….Pages 358-371
A compact data structure and parallel algorithms for permutation graphs….Pages 372-380
Homogeneously orderable graphs and the Steiner tree problem….Pages 381-395