Front matter
1-10
Near-optimal dominating sets in dense random graphs in polynomial expected time
Sotiris E. Nikoletseas and Paul G. Spirakis
11-20
Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality
N. W. Holloway, S. Ravindran and A. M. Gibbons
21-32
Hierarchically specified unit disk graphs
Extended abstract
M. V. Marathe, V. Radhakrishnan, H. B. Hunt and S. S. Ravi
33-44
Bounded tree-width and LOGCFL
Egon Wanke
45-56
On reduction algorithms for graphs with small treewidth
Hans L. Bodlaender
57-69
Algorithms and complexity of sandwich problems in graphs (extended abstract)
Martin Charles Golumbic, Haim Kaplan and Ron Shamir
70-86
On-line graph algorithms for incremental compilation
Alberto Marchetti-Spaccamela, Umberto Nanni and Hans Rohnert
87-98
Average case analysis of fully dynamic connectivity for directed graphs
Paola Alimonti, Stefano Leonardi, Alberto Marchetti-Spacccamela and Xavier Messeguer
99-111
Fully dynamic maintenance of vertex cover
Zoran Ivković and Errol L. Lloyd
112-124
Dynamic algorithms for graphs with treewidth 2
Hans L. Bodlaender
125-131
Short disjoint cycles in graphs with degree constraints
Andreas Brandstädt and Heinz-Jürgen Voss
132-143
Efficient algorithms for tripartitioning triconnected graphs and 3-edge-connected graphs
Koichi Wada and Kimio Kawaguchi
144-152
Towards a solution of the Holyer's problem
Zbigniew Lonc
153-165
Graphs, hypergraphs and hashing
George Havas, Bohdan S. Majewski, Nicholas C. Wormald and Zbigniew J. Czech
166-176
Coloring k-colorable graphs in constant expected parallel time
Luděk Kučera
177-188
Deciding 3-colourability in less than O(1.415n) steps
Ingo Schiermeyer
189-199
A rainbow about T-colorings for complete graphs
Klaus Jansen
200-210
Approximating the chromatic polynomial of a graph
Nai-Wei Lin
211-224
Asteroidal triple-free graphs
Derek. G. Corneil, Stephan Olariu and Lorna Stewart
225-236
The parallel complexity of elimination ordering procedures
Elias Dahlhaus
237-251
Dually chordal graphs
Andreas Brandstädt, Feodor F. Dragan, Victor D. Chepoi and Vitaly I. Voloshin
252-263
The size of reduced OBDDs and optimal read-once branching programs for almost all Boolean functions
Ingo Wegener
264-275
Regular marked Petri nets
Jörg Desel
276-287
The asynchronous committee meeting problem
Javier Esparza and Bernhard von Stengel
288-300
Gossiping in vertex-disjoint paths mode in interconnection networks
Extended abstract
Juraj Hromkovič, Ralf Klasing and Elena A. Stöhr
301-314
The folded Petersen network: A new versatile multiprocessor interconnection topology
Sabine R. Öhring and Sajal K. Das
315-326
Fast load balancing in Cayley graphs and in circuits
Jacques E. Boillat
327-337
Concurrent flows and packet routing in Cayley graphs (Preliminary version)
Farhad Shahrokhi and Laszló A. Székely
338-349
On multi-label linear interval routing schemes
Extended abstract
Evangelos Kranakis, Danny Krizanc and S. S. Ravi
350-363
An ‘All pairs shortest paths’ distributed algorithm using 2n2 messages
S. Haldar
364-375
Linear layouts of generalized hypercubes
Koji Nakano
376-387
Graph ear decompositions and graph embeddings
Extended abstract
Jianer Chen and Saroja P. Kanchi
388-395
Improved bounds for the crossing numbers on surfaces of genus g
Faxhad Shahrokhi, Laszló A. Székely, Ondrej Sýkora and Imrich Vrt'o
396-410
Two algorithms for finding rectangular duals of planar graphs
Goos Kant and Xin He
411-424
A more compact visibility representation
Goos Kant
Back matter