SWAT '90

1. Front Matter

   PDF

2. Structural complexity theory: Recent surprises

   • Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi

   Pages 1-12

   PDF

3. Approximating maximum independent sets by excluding subgraphs

   • Ravi Boppana, Magnús M. Halldórsson

   Pages 13-25

   PDF

4. Generating sparse spanners for weighted graphs

   • Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph

   Pages 26-37

   PDF

5. Finding the k smallest spanning trees

   • David Eppstein

   Pages 38-47

   PDF

6. The file distribution problem for processor networks

   • Goos Kant, Jan van Leeuwen

   Pages 48-59

   PDF

7. Translating polygons with applications to hidden surface removal

   • Mark de Berg

   Pages 60-70

   PDF

8. Output-sensitive generation of the perspective view of isothetic parallelepipeds

   • Franco P. Preparata, Jeffrey Scott Vitter, Mariette Yvinec

   Pages 71-84

   PDF

9. Graphics in flatland revisited

   • Michel Pocchiola

   Pages 85-96

   PDF

10. The visibility diagram: A data structure for visibility problems and motion planning

    • Gert Vegter

    Pages 97-110

    PDF

11. Fast updating of well-balanced trees

    • Arne Andersson, Tony W. Lai

    Pages 111-121

    PDF

12. How to update a balanced binary tree with a constant number of rotations

    • Thomas Ottmann, Derick Wood

    Pages 122-131

    PDF

13. Ranking trees generated by rotations

    • Samuel W. Bent

    Pages 132-142

    PDF

14. Expected behaviour analysis of AVL trees

    • Ricardo Baeza-Yates, Gaston H. Gonnet, Nivio Ziviani

    Pages 143-159

    PDF

15. Analysis of the expected search cost in skip lists

    • Thomas Papadakis, J. Ian Munro, Patricio V. Poblete

    Pages 160-172

    PDF

16. Lower bounds for monotonic list labeling

    • Paul F. Dietz, Ju Zhang

    Pages 173-180

    PDF

17. Sorting shuffled monotone sequences

    • Christos Levcopoulos, Ola Petersson

    Pages 181-191

    PDF

18. A faster parallel algorithm for a matrix searching problem

    • Mikhail J. Atallah

    Pages 192-200

    PDF

19. A rectilinear steiner minimal tree algorithm for convex point sets

    • Dana S. Richards, Jeffrey S. Salowe

    Pages 201-212

    PDF

20. Finding shortest paths in the presence of orthogonal obstacles using a combined L ₁ and link metric

    • Mark de Berg, Marc van Kreveld, Bengt J. Nilsson, Mark H. Overmars

    Pages 213-224

    PDF

This volume presents papers from the 2nd Scandinavian Workshop on Algorithm Theory. The contributions describe original research on algorithms and data structures, in all areas, including combinatorics, computational geometry, parallel computing, and graph theory. The majority of the papers focus on the design and complexity analysis of: data structures, text algorithms, and sequential and parallel algorithms for graph problems and for geometric problems. Examples of tech- niques presented include: - efficient ways to find approximation algorithms for the maximum independent set problem and for graph coloring; - exact estimation of the expected search cost for skip lists; - construction of canonical representations of partial 2-trees and partial 3-trees in linear time; - efficient triangulation of planar point sets and convex polygons.

• Algorithmus
• Approximation
• Datenstrukturen
• Graph
• Komplexität
• algorithms
• complexity
• computational geometry
• data structures
• graph theory
• parallel computing
• algorithm analysis and problem complexity
• combinatorics

Policies and ethics