Algorithm Theory - SWAT 2000

The papers in this volume were presented at SWAT 2000, the Seventh Scandi- vian Workshop on Algorithm Theory. The workshop, which is really a conference, has been held biennially since 1988, rotating between the ve Nordic countries (Sweden, Norway, Finland, Denmark, and Iceland). It also has a loose assoc- tion with the WADS (Workshop on Algorithms and Data Structures) conference that is held in odd numbered years. SWAT is intended as a forum for researchers in the area of design and analysis of algorithms. The SWAT conferences are co- dinated by the SWAT steering committee, which consists of B. Aspvall (Bergen), S. Carlsson (Lule a), H. Hafsteinsson (U. Iceland), R. Karlsson (Lund), A. Lingas (Lund), E. Schmidt (Aarhus), and E. Ukkonen (Helsinki). The call for papers sought contributions in all areas of algorithms and data structures, including computational geometry, parallel and distributed comp- ing, graph theory, and computational biology. A total of 105 papers were s- mitted, out of which the program committee selected 43 for presentation. In addition, invited lectures were presented by Uriel Feige (Weizmann), Mikkel Thorup (AT&T Labs-Research), and Esko Ukkonen (Helsinki). SWAT 2000 was held in Bergen, July 5-7, 2000, and was locally organized by a committee consisting of Pinar Heggernes, Petter Kristiansen, Fredrik Manne, and Jan Arne Telle (chair), all from the department of informatics, University of Bergen.

Includes supplementary material: sn.pub/extras

Inhalt
Invited Talks.- Dynamic Graph Algorithms with Applications.- Coping with the NP-Hardness of the Graph Bandwidth Problem.- Toward Complete Genome Data Mining in Computational Biology.- Data Structures.- A New Trade-Off for Deterministic Dictionaries.- Improved Upper Bounds for Pairing Heaps.- Maintaining Center and Median in Dynamic Trees.- Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n) Update Time.- Graph Algorithms.- A Dynamic Algorithm for Maintaining Graph Partitions.- Data Structures for Maintaining Set Partitions.- Graph Algorithms.- Fixed Parameter Algorithms for Planar Dominating Set and Related Problems.- Embeddings of k-Connected Graphs of Pathwidth k.- On Graph Powers for Leaf-Labeled Trees.- Recognizing Weakly Triangulated Graphs by Edge Separability.- Online Algorithms.- Caching for Web Searching.- On-Line Scheduling with Precedence Constraints.- Scheduling Jobs Before Shut-Down.- Resource Augmentation in Load Balancing.- Fair versus Unrestricted Bin Packing.- Approximation Algorithms.- A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs.- Approximation Algorithms for the Label-Cover MAX and Red-Blue Set Cover Problems.- Approximation Algorithms for Maximum Linear Arrangement.- Approximation Algorithms for Clustering to Minimize the Sum of Diameters.- Matchings.- Robust Matchings and Maximum Clustering.- The Hospitals/Residents Problem with Ties.- Network Design.- Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph.- On the Minimum Augmentation of an ?-Connected Graph to a k-Connected Graph.- Locating Sources to Meet Flow Demands in Undirected Networks.- Improved Greedy Algorithms for Constructing Sparse Geometric Spanners.- Computational Geometry.- Computing the Penetration Depth ofTwo Convex Polytopes in 3D.- Compact Voronoi Diagrams for Moving Convex Polygons.- Efficient Expected-Case Algorithms for Planar Point Location.- A New Competitive Strategy for Reaching the Kernel of an Unknown Polygon.- Strings and Algorithm Engineering.- The Enhanced Double Digest Problem for DNA Physical Mapping.- Generalization of a Suffix Tree for RNA Structural Pattern Matching.- Efficient Computation of All Longest Common Subsequences.- A Blocked All-Pairs Shortest-Paths Algorithm.- External Memory Algorithms.- On External-Memory MST, SSSP, and Multi-way Planar Graph Separation.- I/O-Space Trade-Offs.- Optimization.- Optimal Flow Aggregation.- On the Complexities of the Optimal Rounding Problems of Sequences and Matrices.- On the Complexity of the Sub-permutation Problem.- Parallel Attribute-Efficient Learning of Monotone Boolean Functions.- Distributed Computing and Fault-Tolerance.- Max- and Min-Neighborhood Monopolies.- Optimal Adaptive Fault Diagnosis of Hypercubes.- Fibonacci Correction Networks.- Least Adaptive Optimal Search with Unreliable Tests.