Graph-Theoretic Concepts in Computer Science: 19th International Workshop, WG ’93 Utrecht, The Netherlands, June 16–18, 1993 Proceedings

Sotiris E. Nikoletseas, Paul G. Spirakis (auth.), Jan van Leeuwen (eds.)3540578994, 9783540578994

This 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.

---

Table of contents :
Near-optimal dominating sets in dense random graphs in polynomial expected time….Pages 1-10
Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality….Pages 11-20
Hierarchically specified unit disk graphs….Pages 21-32
Bounded tree-width and LOGCFL….Pages 33-44
On reduction algorithms for graphs with small treewidth….Pages 45-56
Algorithms and complexity of sandwich problems in graphs (extended abstract)….Pages 57-69
On-line graph algorithms for incremental compilation….Pages 70-86
Average case analysis of fully dynamic connectivity for directed graphs….Pages 87-98
Fully dynamic maintenance of vertex cover….Pages 99-111
Dynamic algorithms for graphs with treewidth 2….Pages 112-124
Short disjoint cycles in graphs with degree constraints….Pages 125-131
Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs….Pages 132-143
Towards a solution of the Holyer’s problem….Pages 144-152
Graphs, hypergraphs and hashing….Pages 153-165
Coloring k -colorable graphs in constant expected parallel time….Pages 166-176
Deciding 3-colourability in less than O (1.415 n ) steps….Pages 177-188
A rainbow about T -colorings for complete graphs….Pages 189-199
Approximating the chromatic polynomial of a graph….Pages 200-210
Asteroidal triple-free graphs….Pages 211-224
The parallel complexity of elimination ordering procedures….Pages 225-236
Dually chordal graphs….Pages 237-251
The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions….Pages 252-263
Regular marked Petri nets….Pages 264-275
The asynchronous committee meeting problem….Pages 276-287
Gossiping in vertex-disjoint paths mode in interconnection networks….Pages 288-300
The folded Petersen network: A new versatile multiprocessor interconnection topology….Pages 301-314
Fast load balancing in Cayley graphs and in circuits….Pages 315-326
Concurrent flows and packet routing in Cayley graphs (Preliminary version)….Pages 327-337
On multi-label linear interval routing schemes….Pages 338-349
An ‘All pairs shortest paths’ distributed algorithm using 2 n 2 messages….Pages 350-363
Linear layouts of generalized hypercubes….Pages 364-375
Graph ear decompositions and graph embeddings….Pages 376-387
Improved bounds for the crossing numbers on surfaces of genus g ….Pages 388-395
Two algorithms for finding rectangular duals of planar graphs….Pages 396-410
A more compact visibility representation….Pages 411-424