Algorithms and Data Structures

1. Front Matter

   PDF

2. Computing the all-pairs longest chains in the plane

   • Mikhail J. Atallah, Danny Z. Chen

   Pages 1-13

3. Towards a better understanding of pure packet routing

   • Allan Borodin

   Pages 14-25

4. Tolerating faults in meshes and other networks

   • Richard Cole

   Pages 26-26

5. A generalization of binary search

   • Richard M. Karp

   Pages 27-34

6. Groups and algebraic complexity

   • Andrew C. Yao

   Pages 35-35

7. Connected component and simple polygon intersection searching

   • Pankaj K. Agarwal, Marc van Kreveld

   Pages 36-47

8. An optimal algorithm for finding the separation of simple polygons

   • Nancy M. Amato

   Pages 48-59

9. Balanced search trees made simple

   • Arne Andersson

   Pages 60-71

10. Probing a set of hyperplanes by lines and related problems

    • Yasukazu Aoki, Hiroshi Imai, Keiko Imai, David Rappaport

    Pages 72-82

11. A general lower bound on the I/O-complexity of comparison-based algorithms

    • Lars Arge, Mikael Knudsen, Kirsten Larsen

    Pages 83-94

12. Point probe decision trees for geometric concept classes

    • Esther M. Arkin, Michael T. Goodrich, Joseph S. B. Mitchell, David Mount, Christine D. Piatko, Steven S. Skiena

    Pages 95-106

13. A dynamic separator algorithm

    • Deganit Armon, John Reif

    Pages 107-118

14. Online load balancing of temporary tasks

    • Yossi Azar, Bala Kalyanasundaram, Serge Plotkin, Kirk R. Pruhs, Orli Waarts

    Pages 119-130

15. Connected domination and steiner set on asteroidal triple-free graphs

    • Hari Balakrishnan, Anand Rajaraman, C. Pandu Rangan

    Pages 131-141

16. The complexity of finding certain trees in tournaments

    • R. Balasubramanian, Venkatesh Raman, G. Srinivasaraghavan

    Pages 142-150

17. Spirality of orthogonal representations and optimal drawings of series-parallel graphs and 3-planar graphs (extended abstract)

    • Giuseppe Di Battista, Giuseppe Liotta, Francesco Vargiu

    Pages 151-162

18. Separating the power of EREW and CREW PRAMs with small communication width

    • Paul Beame, Faith E. Fich, Rakesh K. Sinha

    Pages 163-174

19. Triply-logarithmic upper and lower bounds for minimum, range minima, and related problems with integer inputs

    • O. Berkman, Y. Matias, P. Ragde

    Pages 175-187

20. Parallel construction of quadtrees and quality triangulations

    • Marshall Bern, David Eppstein, Shang-Hua Teng

    Pages 188-199

The papers in this volume were presented at the Third Workshop on Algorithmsand Data Structures (WADS '93), held in Montreal, Canada, August 1993. The volume opens with five invited presentations: "Computing the all-pairs longest chains in the plane" by M.J. Atallah and D.Z. Chen, "Towards a better understanding of pure packet routing" by A. Borodin, "Tolerating faults in meshes and other networks" (abstract) by R. Cole, "A generalization of binary search" by R.M. Karp, and "Groups and algebraic complexity" (abstract) by A.C. Yao. The volume continues with 52 regular presentations selected from 165 submissions, each of which was evaluated by at least three program committee members, many of whom called upon additional reviewers.

• Algorithmen
• Algorithms
• Combinatorics
• Complexity Theory
• Datenstrukturen
• Graph Theory
• Kombinatorik
• Komplexitätstheorie
• algorithm
• complexity
• data structure
• data structures
• algorithm analysis and problem complexity

Policies and ethics