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

Susanne Albers (auth.), Thomas Lengauer (eds.)3540572732, 9783540572732, 0387572732

Symposium on Algorithms (ESA ’93), held in Bad Honnef, near Boon, in Germany, September 30 – October 2, 1993. The symposium is intended to launchan annual series of international conferences, held in early fall, covering the field of algorithms. Within the scope of the symposium lies all research on algorithms, theoretical as well as applied, that is carried out in the fields of computer science and discrete applied mathematics. The symposium aims to cater to both of these research communities and to intensify the exchange between them. The volume contains 35 contributed papers selected from 101 proposals submitted in response to the call for papers, as well as three invited lectures: “Evolution of an algorithm” by Michael Paterson, “Complexity of disjoint paths problems in planar graphs” by Alexander Schrijver, and “Sequence comparison and statistical significance in molecular biology” by Michael S. Waterman.

---

Table of contents :
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