Algorithm theory – SWAT 2004 : 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, proceedings

Algorithm Theory - SWAT 2004: 9th Scandinavian Workshop on Algorithm Theory, Humlebæk, Denmark, July 8-10, 2004. Proceedings
Author: Torben Hagerup, Jyrki Katajainen
Published by Springer Berlin Heidelberg
ISBN: 978-3-540-22339-9
DOI: 10.1007/b98413

Table of Contents:

• Design and Analysis of Dynamic Multithreaded Algorithms
• Cache-Oblivious Algorithms and Data Structures
• Getting the Best Response for Your Erg
• Auctions with Budget Constraints
• Tight Approximability Results for Test Set Problems in Bioinformatics
• Robust Subgraphs for Trees and Paths
• Collective Tree Spanners of Graphs
• Optimally Competitive List Batching
• The Relative Worst Order Ratio Applied to Seat Reservation
• Online Maintenance of k-Medians and k-Covers on a Line
• Matching Polyhedral Terrains Using Overlays of Envelopes
• Independent Set of Intersection Graphs of Convex Objects in 2D
• Maximizing the Area of Overlap of Two Unions of Disks Under Rigid Motion
• Construction of the Nearest Neighbor Embracing Graph of a Point Set
• Connectivity of Graphs Under Edge Flips
• Improvement of Nemhauser-Trotter Theorem and Its Applications in Parametrized Complexity
• A Simple Linear-Time Modular Decomposition Algorithm for Graphs, Using Order Extension
• Railway Delay Management: Exploring Its Algorithmic Complexity
• Layered Heaps
• Melding Priority Queues

Includes bibliographical references and index