Algorithms and Data Structures

1. Front Matter

   Pages I-IX

   PDF

2. Optimization over k-set Polytopes and Efficient k-set Enumeration

   • Artur Andrzejak, Komei Fukuda

   Pages 1-12

3. Line Simplification with Restricted Orientations

   • Gabriele Neyer

   Pages 13-24

4. The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout

   • Piotr Berman, Andrew B. Kahng, Devendra Vidhani, Alexander Zelikovsky

   Pages 25-36

5. Resizable Arrays in Optimal Time and Space

   • Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Ian Munro, Robert Sedgewick

   Pages 37-48

6. Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions

   • Rasmus Pagh

   Pages 49-54

7. Design and Analysis of Algorithms for Shared-Memory Multiprocessors

   • Charles E. Leiserson

   Pages 55-55

8. On the Complexity of Orthogonal Compaction

   • Maurizio Patrignani

   Pages 56-61

9. Optimizing Constrained Offset and Scaled Polygonal Annuli

   • Gill Barequet, Prosenjit Bose, Matthew T. Dickerson

   Pages 62-73

10. The Accomodating Function — A Generalization of the Competitive Ratio

    • Joan Boyar, Kim S. Larsen, Morten N. Nielsen

    Pages 74-79

11. Performance Guarantees for the TSP with a Parameterized Triangle Inequality

    • Michael A. Bender, Chandra Chekuri

    Pages 80-85

12. Robot Map Verification of a Graph World

    • Xiaotie Deng, Evangelos Milios, Andy Mirzaian

    Pages 86-97

13. Searching Rectilinear Streets Completely

    • Christoph A. Bröcker, Sven Schuierer

    Pages 98-109

14. General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time

    • Klaus Jansen, Lorant Porkolab

    Pages 110-121

15. The Lazy Bureaucrat Scheduling Problem

    • Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell, Steven S. Skiena

    Pages 122-133

16. Generating 3D Virtual Populations from Pictures of a Few Individuals

    • WonSook Lee, Pierre Beylot, David Sankoff, Nadia Magnenat-Thalmann

    Pages 134-144

17. Testing the Quality of Manufactured Balls

    • Prosenjit Bose, Pat Morin

    Pages 145-156

18. On an Optimal Split Tree Problem

    • S. Rao Kosaraju, Teresa M. Przytycka, Ryan Borgstrom

    Pages 157-168

19. Representing Trees of Higher Degree

    • David Benoit, Erik D. Demaine, J. Ian Munro, Venkatesh Raman

    Pages 169-180

20. Indexing and Dictionary Matching with One Error (Extended Abstract)

    • Amihood Amir, Dmitry Keselman, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein, Michael Rodeh

    Pages 181-192

The papers in this volume were presented at the Sixth Workshop on Algorithms and Data Structures (WADS '99). The workshop took place August 11 - 14, 1999, in Vancouver, Canada. The workshop alternates with the Scandinavian Workshop on Algorithms Theory (SWAT), continuing the tradition of SWAT and WADS starting with SWAT'88 and WADS'89. In response to the program committee's call for papers, 71 papers were submitted. From these submissions, the program committee selected 32 papers for presentation at the workshop. In addition to these submitted papers, the program committee invited the following researchers to give plenary lectures at the workshop: C. Leiserson, N. Magnenat-Thalmann, M. Snir, U. Vazarani, and 1. Vitter. On behalf of the program committee, we would like to express our appreciation to the six plenary lecturers who accepted our invitation to speak, to all the authors who submitted papers to W ADS'99, and to the Pacific Institute for Mathematical Sciences for their sponsorship. Finally, we would like to express our gratitude to all the people who reviewed papers at the request of the program committee. August 1999 F. Dehne A. Gupta J.-R. Sack R. Tamassia VI Conference Chair: A. Gupta Program Committee Chairs: F. Dehne, A. Gupta, J.-R. Sack, R. Tamassia Program Committee: A. Andersson, A. Apostolico, G. Ausiello, G. Bilardi, K. Clarkson, R. Cleve, M. Cosnard, L. Devroye, P. Dymond, M. Farach-Colton, P. Fraigniaud, M. Goodrich, A.

• Complexity
• Data Structures
• Parallel Algorithms
• Scheduling
• Searching Algorithms
• algorithms
• calculus
• hash function
• optimization
• sorting
• verification
• algorithm analysis and problem complexity

• School of Computer Science, Carleton University, Ottawa, Canada

  Frank Dehne, Jörg-Rüdiger Sack

• School of Computer Science, Simon Fraser University, Burnaby, Canada

  Arvind Gupta

• Center for Geometric Computing Providence, Brown University, USA

  Roberto Tamassia

Policies and ethics