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

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