Algorithm Theory - SWAT 2000 [electronic resource] : 7th Scandinavian Workshop on Algorithm Theory Bergen, Norway, July 5-7, 2000 Proceedings /

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.