Algorithm Theory - SWAT 2000 : 7th Scandinavian Workshop on Algorithm Theory Bergen, Norway, July 5-7, 2000, Proceedings

by Halldorsson, Magnus M.

• ISBN13: 9783540676904
• ISBN10: 3540676902
• Format: Paperback
• Copyright: 2000-07-01
• Publisher: Springer Verlag

Summary

This book constitutes the refereed proceedings of the 7th Scandinavian Workshop on Algorithm Theory, SWAT 2000, held in Bergen, Norway, in July 2000.The 43 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from a total of 105 submissions. The papers are organized in sections on data structures, dynamic partitions, graph algorithms, online algorithms, approximation algorithms, matchings, network design, computational geometry, strings and algorithm engineering, external memory algorithms, optimization, and distributed and fault-tolerant computing.

Table of Contents

Invited Talks
Dynamic Graph Algorithms with Applications	1	(9)
Mikkel Thorup
David R. Karger
Coping with the NP-Hardness of the Graph Bandwidth Problem	10	(10)
Uriel Feige
Toward Complete Genome Data Mining in Computational Biology	20	(2)
Esko Ukkonen
Data Structures
A New Trade-Off for Deterministic Dictionaries	22	(10)
Rasmus Pagh
Improved Upper Bounds for Pairing Heaps	32	(14)
John Iacono
Maintaining Center and Median in Dynamic Trees	46	(11)
Stephen Alstrup
Jacob Holm
Mikkel Thorup
Dynamic Planar Convex Hull with Optimal Query Time and O(log n. log log n) Update Time	57	(14)
Gerth Stølting Brodal
Riko Jacob
Dynamic Partitions
A Dynamic Algorithm for Maintaining Graph Partitions	71	(12)
Lyudmil G. Aleksandrov
Hristo N. Djidjev
Data Structures for Maintaining Set Partitions	83	(14)
Michael A. Bender
Saurabh Sethia
Steven Skiena
Graph Algorithms
Fixed Parameter Algorithms for Planar Dominating Set and Related Problems	97	(14)
Jochen Alber
Hans L. Bodlaender
Henning Fernau
Rolf Niedermeier
Embeddings of k-Connected Graphs of Pathwidth k	111	(14)
Arvind Gupta
Naomi Nishimura
Andrzej Proskurowski
Prabhakar Ragde
On Graph Powers for Leaf-Labeled Trees	125	(14)
Naomi Nishimura
Prabhakar Ragde
Dimitrios M. Thilikos
Recognizing Weakly Triangulated Graphs by Edge Separability	139	(11)
Anne Berry
Jean-Paul Bordat
Pinar Heggernes
Online Algorithms
Caching for Web Searching	150	(14)
Bala Kalyanasundaram
John Noga
Kirk Pruhs
Gerhard Woegineger
On-Line Scheduling with Precedence Constraints	164	(11)
Yossi Azar
Leah Epstein
Scheduling Jobs Before Shut-Down	175	(14)
Vincenzo Liberatore
Resource Augmentation in Load Balancing	189	(11)
Yossi Azar
Leah Epstein
Rob van Stee
Fair versus Unrestricted Bin Packing	200	(14)
Yossi Azar
Joan Boyar
Lene M. Favrholdt
Kim S. Larsen
Morten N. Nielsen
Approximation Algorithms
A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs	214	(6)
Piotr Berman
Approximation Algorithms for the Label-Cover Max and Red-Blue Set Cover Problems	220	(11)
David Peleg
Approximation Algrithms for Maximum Linear Arrangement	231	(6)
Refael Hassin
Shlomi Rubinstein
Approximation Algorithms for Clustering Minimize the Sum of Diameters	237	(14)
Srinivas R. Doddi
Madhav V. Marathe
S. S. Ravi
David Scot Taylor
Peter Widmayer
Matchings
Robust Matchings and Maximum Clustering	251	(8)
Refael Hassin
Shlomi Rubinstein
The Hospitals/Residents Problem with Ties	259	(13)
Robert W. Irving
David F. Manlove
Sandy Scott
Network Design
Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph	272	(14)
Yefim Dinitz
Ronit Nossenson
On the Minimum Augmentation of an l-Connected Graph to a k-Connected Graph	286	(14)
Toshimasa Ishii
Hiroshi Nagamochi
Locating Sources to Meet Flow Demands in Undirected Networks	300	(14)
Kouji Arata
Satoru Iwata
Kazuhisa Makino
Satoru Fujishige
Improved Greedy Algorithms for Constructing Sparse Geometric Spanners	314	(14)
Joachim Gudmundsson
Christos Levcopoulos
Giri Narasimhan
Computational Geometry
Computing the Penetration Depth of Two Convex Polytopes in 3D	328	(11)
Pankaj K. Agarwal
Leonidas J. Guibas
Sariel Har-Peled
Alexander Rabinovitch
Micha Sharir
Compact Voronoi Diagrams for Moving Convex Polygons	339	(14)
Leonidas J. Guibas
Jack Snoeyink
Li Zhang
Efficent Expected-Case Algorithms for Planar Point Location	353	(14)
Sunil Arya
Siu-Wing Cheng
David M. Mount
H. Ramesh
A New Competitive Strategy for Reaching the Kernel of an Unknown Polygon	367	(16)
Leonidas Palios
Strings and Algorithm Engineering
The Enhanced Double Digest Problem for DNA Physical Mapping	383	(10)
Ming- Yang Kao
Jared Samet
Wing-Kin Sung
Generalization of a Suffix Tree for RNA Structural Pattern Matching	393	(14)
Tetsuo Shibuya
Efficient Computation of All Longest Common Subsequences	407	(12)
Claus Rick
A Blocked All-Pairs Shortest-Paths Algorithm	419	(14)
Gayathri Venkataraman
Sartaj Sahni
Srabani Mukhopadhyaya
External Memory Algorithms
On External-Memory MST, SSSP, and Multi-way Planar Graph Separation	433	(15)
Lars Arge
Gerth Stølting Brodal
Laura Toma
I/O-Space Trade-Offs	448	(14)
Lars Arge
Jakob Pagter
Optimization
Optimal Flow Aggregation	462	(14)
Subhash Suri
Tuomas Sandholm
Priyank Ramesh Warkhede
On the Complexities of the Optimal Rounding Problems of Sequences and Matrices	476	(14)
Tetsuo Asano
Tomomi Matsui
Takeshi Tokuyama
On the Complexity of the Sub-permutation Problem	490	(14)
Shlomo Ahal
Yuri Rabinovich
Parallel Attribute-Efficient Learning of Monotone Boolean Functions	504	(9)
Peter Damaschke
Distributed Computing and Fault-Tolerance
Max- and Min-Neighborhood Monopolies	513	(14)
Kazuhisa Makino
Masafumi Yamashita
Tiko Kameda
Optimal Adaptive Fault Diagnosis of Hypercubes	527	(8)
Andreas Bjorklund
Fibonacci Correction Networks	535	(14)
Grzegorz Stachowiak
Least Adaptive Optimal Search with Unreliable Tests	549	(14)
Ferdinando Cicalese
Ugo Vaccaro
Daniele Mundici
Author Index	563