Algorithms - ESA '93

1. Front Matter

   PDF

2. The influence of lookahead in competitive paging algorithms

   • Susanne Albers

   Pages 1-12

3. An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications

   • Mikhail J. Atallah, Danny Z. Chen, D. T. Lee

   Pages 13-24

4. Efficient self simulation algorithms for reconfigurable arrays

   • Yosi Ben-Asher, Dan Gordon, Assaf Schuster

   Pages 25-36

5. Optimal upward planarity testing of single-source digraphs

   • Paola Bertolazzi, Giuseppe Di Battista, Carlo Mannino, Roberto Tamassia

   Pages 37-48

6. On bufferless routing of variable-length messages in leveled networks

   • S. N. Bhatt, G. Bilardi, G. Pucci, A. Ranade, A. L. Rosenberg, E. J. Schwabe

   Pages 49-60

7. Saving comparisons in the Crochemore-Perrin string matching algorithm

   • Dany Breslauer

   Pages 61-72

8. Unambiguity of extended regular expressions in SGML document grammars

   • Anne Brüggemann-Klein

   Pages 73-84

9. On the direct sum conjecture in the straight line model

   • Nader H. Bshouty

   Pages 85-96

10. Combine and conquer: A general technique for dynamic algorithms

    • Robert F. Cohen, Roberto Tamassia

    Pages 97-108

11. Optimal CREW-PRAM algorithms for direct dominance problems

    • Amitava Datta, Anil Maheshwari, Jörg-Rüdiger Sack

    Pages 109-120

12. Trekking in the Alps without freezing or getting tired

    • Mark de Berg, Marc van Kreveld

    Pages 121-132

13. Dog bites postman: Point location in the moving Voronoi diagram and related problems

    • Olivier Devillers, Mordecai Golin

    Pages 133-144

14. Parallel approximation schemes for problems on planar graphs

    • J. Díaz, M. J. Serna, J. Torán

    Pages 145-156

15. DNA physical mapping: Three ways difficult

    • Michael R. Fellows, Michael T. Hallett, H. Todd Wareham

    Pages 157-168

16. A calculus of random generation

    • Philippe Flajolet, Paul Zimmermann, Bernard van Cutsem

    Pages 169-180

17. The bit complexity of distributed sorting

    • O. Gerstel, S. Zaks

    Pages 181-191

18. Three-clustering of points in the plane

    • Johann Hagauer, Günter Rote

    Pages 192-199

19. Gossiping in vertex-disjoint paths mode in d-dimensional grids and planar graphs

    • Juraj Hromkovič, Ralf Klasing, Elena A. Stöhr, Hubert Wagener

    Pages 200-211

20. Fully dynamic planarity testing in planar embedded graphs

    • Giuseppe F. Italiano, Johannes A. La Poutré, Monika H. Rauch

    Pages 212-223

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.

• Algorithmen
• Algorithms
• Combinatorics
• Discrete Mathematics
• Graphs
• Kombinatorik
• Komplexität
• STATISTICA
• algorithm
• complexity
• computer
• computer science
• algorithm analysis and problem complexity

Policies and ethics