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

Mikkel Thorup, David R. Karger (auth.)3540676902, 9783540676904

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 :
Dynamic Graph Algorithms with Applications….Pages 1-9
Coping with the NP-Hardness of the Graph Bandwidth Problem….Pages 10-19
Toward Complete Genome Data Mining in Computational Biology….Pages 20-21
A New Trade-Off for Deterministic Dictionaries….Pages 22-31
Improved Upper Bounds for Pairing Heaps….Pages 32-45
Maintaining Center and Median in Dynamic Trees….Pages 46-56
Dynamic Planar Convex Hull with Optimal Query Time and O(log n · log log n ) Update Time….Pages 57-70
A Dynamic Algorithm for Maintaining Graph Partitions….Pages 71-82
Data Structures for Maintaining Set Partitions….Pages 83-96
Fixed Parameter Algorithms for P lanar D ominating S et and Related Problems….Pages 97-110
Embeddings of k-Connected Graphs of Pathwidth k….Pages 111-124
On Graph Powers for Leaf-Labeled Trees….Pages 125-138
Recognizing Weakly Triangulated Graphs by Edge Separability….Pages 139-149
Caching for Web Searching….Pages 150-163
On-Line Scheduling with Precedence Constraints….Pages 164-174
Scheduling Jobs Before Shut-Down….Pages 175-188
Resource Augmentation in Load Balancing….Pages 189-199
Fair versus Unrestricted Bin Packing….Pages 200-213
A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs….Pages 214-219
Approximation Algorithms for the Label-Cover MAX and Red-Blue Set Cover Problems….Pages 220-231
Approximation Algorithms for Maximum Linear Arrangement….Pages 231-236
Approximation Algorithms for Clustering to Minimize the Sum of Diameters….Pages 237-250
Robust Matchings and Maximum Clustering….Pages 251-258
The Hospitals/Residents Problem with Ties….Pages 259-271
Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph….Pages 272-285
On the Minimum Augmentation of an ℓ-Connected Graph to a k-Connected Graph….Pages 286-299
Locating Sources to Meet Flow Demands in Undirected Networks….Pages 300-313
Improved Greedy Algorithms for Constructing Sparse Geometric Spanners….Pages 314-328
Computing the Penetration Depth of Two Convex Polytopes in 3D….Pages 328-338
Compact Voronoi Diagrams for Moving Convex Polygons….Pages 339-352
Efficient Expected-Case Algorithms for Planar Point Location….Pages 353-366
A New Competitive Strategy for Reaching the Kernel of an Unknown Polygon….Pages 367-382
The Enhanced Double Digest Problem for DNA Physical Mapping….Pages 383-392
Generalization of a Suffix Tree for RNA Structural Pattern Matching….Pages 393-406
Efficient Computation of All Longest Common Subsequences….Pages 407-418
A Blocked All-Pairs Shortest-Paths Algorithm….Pages 419-432
On External-Memory MST, SSSP, and Multi-way Planar Graph Separation….Pages 433-447
I/O-Space Trade-Offs….Pages 448-461
Optimal Flow Aggregation….Pages 462-475
On the Complexities of the Optimal Rounding Problems of Sequences and Matrices….Pages 476-489
On the Complexity of the Sub-permutation Problem….Pages 490-503
Parallel Attribute-Efficient Learning of Monotone Boolean Functions….Pages 504-512
Max- and Min-Neighborhood Monopolies….Pages 513-526
Optimal Adaptive Fault Diagnosis of Hypercubes….Pages 527-534
Fibonacci Correction Networks….Pages 535-548
Least Adaptive Optimal Search with Unreliable Tests….Pages 559-562