Skip to main content
SpringerLink
Log in

Algorithms and Data Structures

6th International Workshop, WADS'99 Vancouver, Canada, August 11-14, 1999 Proceedings

  • Conference proceedings
  • © 1999

Overview

Editors:
  1. Frank Dehne

    1. School of Computer Science, Carleton University, Ottawa, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Jörg-Rüdiger Sack

    1. School of Computer Science, Carleton University, Ottawa, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Arvind Gupta

    1. School of Computer Science, Simon Fraser University, Burnaby, Canada

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  4. Roberto Tamassia

    1. Center for Geometric Computing Providence, Brown University, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 1663)

Included in the following conference series:

Conference proceedings info: WADS 1999.

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (35 papers)

  1. Front Matter

    Pages I-IX
    Download chapter 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
Back to top

Other volumes

  1. Algorithms and Data Structures

Keywords

About this book

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.

Editors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation