Graph-Theoretic Concepts in Computer Science: 23rd International Workshop, WG’97 Berlin, Germany, June 18–20, 1997 Proceedings

David P. Williamson (auth.), Rolf H. Möhring (eds.)3540637575, 9783540637578

This book constitutes the strictly refereed post-workshop proceedings of the 23rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG’97, held in Berlin, Germany in June 1997.
The volume presents 28 revised full papers carefully selected for inclusion in the book from 42 submissions. The papers address a variety of graph-theoretic issues relevant from the computer science point of view such as graph algorithms, cycles, graph decompositions, interconnection networks, local search, graph orderings, graph matching, graph languages, tree-width computation, etc.

---

Table of contents :
Gadgets, approximation, and linear programming: Improved hardness results for cut and satisfiability problems….Pages 1-1
Non-oblivious local search for MAX 2-CCSP with application to MAX DICUT….Pages 2-14
On the number of simple cycles in planar graphs….Pages 15-24
On the separable-homogeneous decomposition of graphs….Pages 25-37
Pseudo-hamiltonian graphs….Pages 38-51
Acyclic orientations for deadlock prevention in interconnection networks….Pages 52-64
Weak-order extensions of an order….Pages 65-77
An upper bound for the maximum cut mean value….Pages 78-84
NP -completeness results for minimum planar spanners….Pages 85-99
Computing the independence number of dense triangle-free graphs….Pages 100-108
Algorithms for the treewidth and minimum fill-in of HHD-free graphs….Pages 109-117
Block decomposition of inheritance hierarchies….Pages 118-131
Minimal elimination ordering inside a given chordal graph….Pages 132-143
On-line algorithms for networks of temporal constraints….Pages 144-156
Parallel algorithms for treewidth two….Pages 157-170
On optimal graphs embedded into paths and rings, with analysis using l 1 -spheres….Pages 171-183
On greedy matching ordering and greedy matchable graphs….Pages 184-198
Off-line and on-line call-scheduling in stars and trees….Pages 199-213
Computational complexity of the Krausz dimension of graphs….Pages 214-228
Asteroidal sets in graphs….Pages 229-241
Complexity of colored graph covers I. Colored directed multigraphs….Pages 242-257
A syntactic approach to random walks on graphs….Pages 258-272
Bicliques in graphs II: Recognizing k -path graphs and underlying graphs of line digraphs….Pages 273-287
Large networks with small diameter….Pages 288-302
The bounded tree-width problem of context-free graph languages….Pages 303-317
Structured programs have small tree-width and good register allocation….Pages 318-332
A measure of parallelization for the lexicographically first maximal subgraph problems….Pages 333-341
Make your enemies transparent….Pages 342-353
Optimal fault-tolerant ATM-routings for biconnected graphs….Pages 354-367