Graph-Theoretic Concepts in Computer Science: 22nd International Workshop, WG ’96 Cadenabbia, Italy, June 12–14, 1996 Proceedings

Andrew C. Yao (auth.), Fabrizio d’Amore, Paolo Giulio Franciosa, Alberto Marchetti-Spaccamela (eds.)3540625593, 9783540625599

This book constitutes the carefully refereed post-proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, WG ’96, held in Cadenabbia, Italy, in June 1996.
The 30 revised full papers presented in the volume were selected from a total of 65 submissions. This collection documents the state of the art in the area. Among the topics addressed are graph algorithms, graph rewriting, hypergraphs, graph drawing, networking, approximation and optimization, trees, graph computation, and others.

---

Table of contents :
Hypergraphs and decision trees….Pages 1-1
Improved approximations of independent dominating set in bounded degree graphs….Pages 2-16
A new characterization of P 4 -connected graphs….Pages 17-30
Node rewriting in hypergraphs….Pages 31-43
On κ-partitioning the n-cube….Pages 44-55
Embedding complete binary trees in product graphs….Pages 56-66
Clique and anticlique partitions of graphs….Pages 67-72
Optimal parallel routing in star graphs….Pages 73-84
Counting edges in a dag….Pages 85-100
Closure properties of context-free Hyperedge Replacement Systems….Pages 101-113
Upward drawings of search trees….Pages 114-125
More general parallel tree contraction: Register allocation and broadcasting in a tree….Pages 126-140
System diagnosis with smallest risk of error….Pages 141-150
Efficient algorithms for shortest path queries in planar digraphs….Pages 151-165
LexBFS-orderings and powers of graphs….Pages 166-180
Efficient Union-Find for planar graphs and other sparse graph classes….Pages 181-195
Switchbox routing in VLSI design: Closing the complexity gap….Pages 196-210
Detecting diamond necklaces in labeled dags….Pages 211-223
Algebraic graph derivations for graphical calculi….Pages 224-238
Definability equals recognizability of partial 3-trees….Pages 239-253
One, two, three, many, or: Complexity aspects of dynamic network flows with dedicated arcs….Pages 254-267
Approximate maxima finding of continuous functions under restricted budget (Extended abstract)….Pages 268-278
The Optimal Cost Chromatic Partition problem for trees and interval graphs….Pages 279-292
Modifying networks to obtain low cost trees….Pages 293-307
On the hardness of allocating frequencies for hybrid networks….Pages 308-322
Homogeneous sets and domination problems….Pages 323-337
Independent spanning trees of product graphs….Pages 338-351
Designing distrance-preserving fault-tolerant topologies….Pages 352-366
Shortest path algorithms for nearly acyclic directed graphs….Pages 367-374
Computing disjoint paths with length constraints….Pages 375-389
Generalized edge-rankings of trees….Pages 390-404