Skip to main content
SpringerLink
Log in

Algorithm Theory - SWAT 2002

8th Scandinavian Workshop on Algorithm Theory, Turku, Finland, July 3-5, 2002 Proceedings

  • Conference proceedings
  • © 2002

Overview

Editors:
  1. Martti Penttonen

    1. Department of Computer Science and Applied Mathematics, University of Kuopio, Kuopio, Finland

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Erik Meineche Schmidt

    1. BRICS, University of Aarhus, Department of Computer Science, Aarhus C, 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 2368)

Included in the following conference series:

Conference proceedings info: SWAT 2002.

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

  1. Front Matter

    Pages I-XIV
    Download chapter PDF

  2. Invited Speakers

    1. An Efficient Quasidictionary

      • Torben Hagerup, Rajeev Raman
      Pages 1-18

    2. Combining Pattern Discovery and Probabilistic Modeling in Data Mining

      • Heikki Mannila
      Pages 19-19

  3. Scheduling

    1. Time and Space Efficient Multi-method Dispatching

      • Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz, Theis Rauhe
      Pages 20-29

    2. Linear Time Approximation Schemes for Vehicle Scheduling

      • John E. Augustine, Steven S. Seiden
      Pages 30-39

    3. Minimizing Makespan for the Lazy Bureaucrat Problem

      • Clint Hepner, Cliff Stein
      Pages 40-50

    4. A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times

      • Monaldo Mastrolilli
      Pages 51-59

  4. Computational Geometry

    1. Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains

      • Stephan Eidenbenz
      Pages 60-68

    2. Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D

      • Partha P. Goswami, Sandip Das, Subhas C. Nandy
      Pages 69-79

    3. Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains

      • Christos Levcopoulos, Andrzej Lingas, Joseph S. B. Mitchell
      Pages 80-89

    4. Exact Algorithms and Approximation Schemes for Base Station Placement Problems

      • Nissan Lev-Tov, David Peleg
      Pages 90-99

    5. A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels

      • Zhongping Qin, Binhai Zhu
      Pages 100-109

    6. Optimal Algorithm for a Special Point-Labeling Problem

      • Sasanka Roy, Partha P. Goswami, Sandip Das, Subhas C. Nandy
      Pages 110-120

    7. Random Arc Allocation and Applications

      • Peter Sanders, Berthold Vöcking
      Pages 121-130

    8. On Neighbors in Geometric Permutations

      • Micha Sharir, Shakhar Smorodinsky
      Pages 131-139

  5. Graph Algorithms

    1. Powers of Geometric Intersection Graphs and Dispersion Algorithms

      • Geir Agnarsson, Peter Damaschke, Magnús M. Halldórsson
      Pages 140-149

    2. Efficient Data Reduction for Dominating Set: A Linear Problem Kernel for the Planar Case

      • Jochen Alber, Michael R. Fellows, Rolf Niedermeier
      Pages 150-159

    3. Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous

      • Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger
      Pages 160-169

    4. Approximation Hardness of the Steiner Tree Problem on Graphs

      • Miroslav Chlebík, Janka Chlebíková
      Pages 170-179

    5. The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus

      • J. Ellis, H. Fan, M. Fellows
      Pages 180-189
Back to top

Other volumes

  1. Algorithm Theory — SWAT 2002

Keywords

Editors and Affiliations

  • Department of Computer Science and Applied Mathematics, University of Kuopio, Kuopio, Finland

    Martti Penttonen

  • BRICS, University of Aarhus, Department of Computer Science, Aarhus C, Denmark

    Erik Meineche Schmidt

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation