Algorithm Theory - SWAT '94

1. Front Matter

   PDF

2. Computing depth orders and related problems

   • Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

   Pages 1-12

3. Selection in monotone matrices and computing k ^th nearest neighbors

   • Pankaj K. Agarwal, Sandeep Sen

   Pages 13-24

4. New on-line algorithms for the page replication problem

   • Susanne Albers, Hisashi Koga

   Pages 25-36

5. Serving requests with on-line routing

   • Giorgio Ausiello, Esteban Feuerstein, Stefano Leonardi, Leen Stougie, Maurizio Talamo

   Pages 37-48

6. A new algorithm for the construction of optimal B-trees

   • Peter Becker

   Pages 49-60

7. New results on binary space partitions in the plane (extended abstract)

   • Mark de Berg, Marko de Groot, Mark Overmars

   Pages 61-72

8. A nearly optimal parallel algorithm for the Voronoi diagram of a convex polygon

   • Piotr Berman, Andrzej Lingas

   Pages 73-82

9. On triangulating planar graphs under the four-connectivity constraint

   • Therese Biedl, Goos Kant, Michael Kaufmann

   Pages 83-94

10. Parallel and sequential approximation of shortest superstrings

    • Artur Czumaj, Leszek Gasieniec, Marek Piotrów, Wojciech Rytter

    Pages 95-106

11. Separating translates in the plane: Combinatorial bounds and an algorithm

    • Jurek Czyzowicz, Hazel Everett, Jean-Marc Robert

    Pages 107-118

12. Finding all weakly-visible chords of a polygon in linear time

    • Gautam Das, Paul J. Heffernan, Giri Narasimhan

    Pages 119-130

13. A tight lower bound for on-line monotonic list labeling

    • Paul F. Dietz, Joel I. Seiferas, Ju Zhang

    Pages 131-142

14. Trapezoid graphs and generalizations, geometry and algorithms

    • Stefan Felsner, Rudolf Müller, Lorenz Wernisch

    Pages 143-154

15. Optimal parametric search on graphs of bounded tree-width

    • David Fernández-Baca, Giora Slutzki

    Pages 155-166

16. Lower bounds for dynamic algorithms

    • Michael L. Fredman

    Pages 167-171

17. Sequential and parallel algorithms for embedding problems on classes of partial k-trees

    • Arvind Gupta, Naomi Nishimura

    Pages 172-182

18. On intersection searching problems involving curved objects

    • Prosenjit Gupta, Ravi Janardan, Michiel Smid

    Pages 183-194

19. Improved approximations of independent sets in bounded-degree graphs

    • Magnús M. Halldórsson, Jaikumar Radhakrishnan

    Pages 195-206

20. Asymptotically optimal election on weighted rings

    • Lisa Higham, Teresa Przytycka

    Pages 207-218

This volume constitutes the proceedings of SWAT '94, the 4th Scandinavian Workshop on Algorithm Theory, held in Aarhus, Denmark in July 1994. The SWAT events are organized each even year and alternate with the WADS meetings (Workshops on Algorithms and Data Structures) held each odd year in North America.
The volume contains 31 papers selected from a total of 100 submissions and 3 invited presentations by Michael Fredman (Rutgers), Johan Hastad (Stockholm), and Ketan Mulmuley (Chicago). The contributions cover algorithms and data structures in all areas of computer science and in discrete mathematics, particularly including graph theory, computational geometry, and databases.

• Algorithmen
• Computer-Geometrie
• Datenstrukturen
• Graph Algorithms
• Graph-Algorithmen
• Voronoi Diagrams
• Voronoi-Diagramme
• algorithms
• computational geometry
• data structures
• algorithm analysis and problem complexity

Policies and ethics