Skip to main content
SpringerLink
Log in
Book cover

Algorithm Theory - SWAT 2004

9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings

  • Conference proceedings
  • © 2004

Overview

Editors:
  1. Torben Hagerup

    1. Institut für Informatik, Universität Augsburg, Augsburg, Germany

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Jyrki Katajainen

    1. Department of Computing, University of Copenhagen, Denmark

    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 3111)

Included in the following conference series:

Conference proceedings info: SWAT 2004.

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 (42 papers)

  1. Front Matter

    Download chapter PDF

  2. Invited Contributions

    1. Design and Analysis of Dynamic Multithreaded Algorithms

      • Charles E. Leiserson
      Pages 1-2

    2. Cache-Oblivious Algorithms and Data Structures

      • Gerth Stølting Brodal
      Pages 3-13

  3. Refereed Contributions

    1. Getting the Best Response for Your Erg

      • Kirk Pruhs, Patchrawat Uthaisombut, Gerhard Woeginger
      Pages 14-25

    2. Auctions with Budget Constraints

      • Nir Andelman, Yishay Mansour
      Pages 26-38

    3. Tight Approximability Results for Test Set Problems in Bioinformatics

      • Piotr Berman, Bhaskar DasGupta, Ming-Yang Kao
      Pages 39-50

    4. Robust Subgraphs for Trees and Paths

      • Refael Hassin, Danny Segev
      Pages 51-63

    5. Collective Tree Spanners of Graphs

      • Feodor F. Dragan, Chenyu Yan, Irina Lomonosov
      Pages 64-76

    6. Optimally Competitive List Batching

      • Wolfgang W. Bein, Leah Epstein, Lawrence L. Larmore, John Noga
      Pages 77-89

    7. The Relative Worst Order Ratio Applied to Seat Reservation

      • Joan Boyar, Paul Medvedev
      Pages 90-101

    8. Online Maintenance of k-Medians and k-Covers on a Line

      • Rudolf Fleischer, Mordecai J. Golin, Yan Zhang
      Pages 102-113

    9. Matching Polyhedral Terrains Using Overlays of Envelopes

      • Vladlen Koltun, Carola Wenk
      Pages 114-126

    10. Independent Set of Intersection Graphs of Convex Objects in 2D

      • Pankaj K. Agarwal, Nabil H. Mustafa
      Pages 127-137

    11. Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion

      • Mark de Berg, Sergio Cabello, Panos Giannopoulos, Christian Knauer, René van Oostrum, Remco C. Veltkamp
      Pages 138-149

    12. Construction of the Nearest Neighbor Embracing Graph of a Point Set

      • M. Y. Chan, Danny Chen, Francis Y. L. Chin, Cao An Wang
      Pages 150-160

    13. Connectivity of Graphs Under Edge Flips

      • Norbert Zeh
      Pages 161-173

    14. Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity

      • Miroslav Chlebík, Janka Chlebíková
      Pages 174-186

    15. A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension

      • Michel Habib, Fabien de Montgolfier, Christophe Paul
      Pages 187-198

    16. Railway Delay Management: Exploring Its Algorithmic Complexity

      • Michael Gatto, Björn Glaus, Riko Jacob, Leon Peeters, Peter Widmayer
      Pages 199-211

    17. Layered Heaps

      • Amr Elmasry
      Pages 212-222
Back to top

Other volumes

  1. Algorithm Theory - SWAT 2004

Keywords

Editors and Affiliations

  • Institut für Informatik, Universität Augsburg, Augsburg, Germany

    Torben Hagerup

  • Department of Computing, University of Copenhagen, Denmark

    Jyrki Katajainen

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation