Algorithm Theory - SWAT 2000

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.

Includes supplementary material: sn.pub/extras