Algorithms—ESA '93: First Annual European Symposium Bad Honnef, Germany September 30–October 2, 1993 Proceedings

The influence of lookahead in competitive paging algorithms....Pages 1-12
An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications....Pages 13-24
Efficient self simulation algorithms for reconfigurable arrays....Pages 25-36
Optimal upward planarity testing of single-source digraphs....Pages 37-48
On bufferless routing of variable-length messages in leveled networks....Pages 49-60
Saving comparisons in the Crochemore-Perrin string matching algorithm....Pages 61-72
Unambiguity of extended regular expressions in SGML document grammars....Pages 73-84
On the direct sum conjecture in the straight line model....Pages 85-96
Combine and conquer: A general technique for dynamic algorithms....Pages 97-108
Optimal CREW-PRAM algorithms for direct dominance problems....Pages 109-120
Trekking in the Alps without freezing or getting tired....Pages 121-132
Dog bites postman: Point location in the moving Voronoi diagram and related problems....Pages 133-144
Parallel approximation schemes for problems on planar graphs....Pages 145-156
DNA physical mapping: Three ways difficult....Pages 157-168
A calculus of random generation....Pages 169-180
The bit complexity of distributed sorting....Pages 181-191
Three-clustering of points in the plane....Pages 192-199
Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs....Pages 200-211
Fully dynamic planarity testing in planar embedded graphs....Pages 212-223
Fully dynamic algorithms for bin packing: Being (mostly) myopic helps....Pages 224-235
Increasing the vertex-connectivity in directed graphs....Pages 236-247
On the recognition of permuted bottleneck monge matrices....Pages 248-259
Computing treewidth and minimum fill-in: All you need are the minimal separators....Pages 260-271
Block gossiping on grids and tori: Deterministic sorting and routing match the bisection bound....Pages 272-283
The complexity of scheduling trees with communication delays....Pages 284-294
Optimal tree contraction on the hypercube and related networks....Pages 295-305
Evolution of an algorithm....Pages 306-308
Mesh connected computers with fixed and reconfigurable buses: Packet routing, sorting, and selection....Pages 309-320
An efficient parallel algorithm for the layered planar monotone circuit value problem....Pages 321-332
Randomized routing on meshes with buses....Pages 333-344
On the distribution of the transitive closure in a random acyclic digraph....Pages 345-356
Complexity of disjoint paths problems in planar graphs....Pages 357-359
Integer multicommodity flows with reduced demands....Pages 360-371
A fully dynamic data structure for reachability in planar digraphs....Pages 372-383
A linear-time algorithm for edge-disjoint paths in planar graphs....Pages 384-395
Sequence comparison and statistical significance in molecular biology....Pages 396-396
Surface reconstruction between simple polygons via angle criteria....Pages 397-408
A linear algorithm for edge-coloring partial k -trees....Pages 409-418