7. SWAT 2000: Bergen, Norway

Invited Talks

• Mikkel Thorup:
  Dynamic Graph Algorithms with Applications. 1-9
  
• Uriel Feige:
  Coping with the NP-Hardness of the Graph Bandwidth Problem. 10-19
  
• Esko Ukkonen:
  Toward Complete Genome Data Mining in Computational Biology. 20-21
  

Data Structures

• Rasmus Pagh:
  A New Trade-Off for Deterministic Dictionaries. 22-31
  
• John Iacono:
  Improved Upper Bounds for Pairing Heaps. 32-45
  
• Stephen Alstrup, Jacob Holm, Mikkel Thorup:
  Maintaining Center and Median in Dynamic Trees. 46-56
  
• Gerth Stølting Brodal, Riko Jacob:
  Dynamic Planar Convex Hull with Optimal Query Time. 57-70
  

Dynamic Partitions

• Lyudmil Aleksandrov, Hristo Djidjev:
  A Dynamic Algorithm for Maintaining Graph Partitions. 71-82
  
• Michael A. Bender, Saurabh Sethia, Steven Skiena:
  Data Structures for Maintaining Set Partitions. 83-96
  

Graph Algorithms

• Jochen Alber, Hans L. Bodlaender, Henning Fernau, Rolf Niedermeier:
  Fixed Parameter Algorithms for PLANAR DOMINATING SET and Related Problems. 97-110
  
• Arvind Gupta, Naomi Nishimura, Andrzej Proskurowski, Prabhakar Ragde:
  Embeddings of k-Connected Graphs of Pathwidth k. 111-124
  
• Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos:
  On Graph Powers for Leaf-Labeled Trees. 125-138
  
• Anne Berry, Jean Paul Bordat, Pinar Heggernes:
  Recognizing Weakly Triangulated Graphs by Edge Separability. 139-149
  

Online Algorithms

• Bala Kalyanasundaram, John Noga, Kirk Pruhs, Gerhard J. Woeginger:
  Caching for Web Searching. 150-163
  
• Yossi Azar, Leah Epstein:
  On-Line Scheduling with Precedence Constraints. 164-174
  
• Vincenzo Liberatore:
  Scheduling Jobs Before Shut-Down. 175-188
  
• Yossi Azar, Leah Epstein, Rob van Stee:
  Resource Augmentation in Load Balancing. 189-199
  
• Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, Morten N. Nielsen:
  Fair versus Unrestricted Bin Packing. 200-213
  

Approximation Algorithms

• Piotr Berman:
  A d/2 Approximation for Maximum Weight Independent Set in d-Claw Free Graphs. 214-219
  
• David Peleg:
  Approximation Algorithms for the Label-Cover_MAX and Red-Blue Set Cover Problems. 220-230
  
• Refael Hassin, Shlomi Rubinstein:
  Approximation Algorithms for Maximum Linear Arrangement. 231-236
  
• Srinivas Doddi, Madhav V. Marathe, S. S. Ravi, David Scot Taylor, Peter Widmayer:
  Approximation Algorithms for Clustering to Minimize the Sum of Diameters. 237-250
  

Matchings

• Refael Hassin, Shlomi Rubinstein:
  Robust Matchings and Maximum Clustering. 251-258
  
• Robert W. Irving, David Manlove, Sandy Scott:
  The Hospitals/Residents Problem with Ties. 259-271
  

Network Design

• Yefim Dinitz, Ronit Nossenson:
  Incremental Maintenance of the 5-Edge-Connectivity Classes of a Graph. 272-285
  
• Toshimasa Ishii, Hiroshi Nagamochi:
  On the Minimum Augmentation of an l-Connected Graph to a k-Connected Graph. 286-299
  
• Kouji Arata, Satoru Iwata, Kazuhisa Makino, Satoru Fujishige:
  Locating Sources to Meet Flow Demands in Undirected Networks. 300-313
  
• Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan:
  Improved Greedy Algorithms for Constructing Sparse Geometric Spanners. 314-327
  

Computational Geometry

• Pankaj K. Agarwal, Leonidas J. Guibas, Sariel Har-Peled, Alexander Rabinovitch, Micha Sharir:
  Computing the Penetration Depth of Two Convex Polytopes in 3D. 328-338
  
• Leonidas J. Guibas, Jack Snoeyink, Li Zhang:
  Compact Voronoi Diagrams for Moving Convex Polygons. 339-352
  
• Sunil Arya, Siu-Wing Cheng, David M. Mount, Ramesh Hariharan:
  Efficient Expected-Case Algorithms for Planar Point Location. 353-366
  
• Leonidas Palios:
  A New Competitive Strategy for Reaching the Kernel of an Unknown Polygon. 367-382
  

Strings and Algorithm Engineering

• Ming-Yang Kao, Jared Samet, Wing-Kin Sung:
  The Enhanced Double Digest Problem for DNA Physical Mapping. 383-392
  
• Tetsuo Shibuya:
  Generalization of a Suffix Tree for RNA Structural Pattern Matching. 393-406
  
• Claus Rick:
  Efficient Computation of All Longest Common Subsequences. 407-418
  
• Gayathri Venkataraman, Sartaj Sahni, Srabani Mukhopadhyaya:
  A Blocked All-Pairs Shortest-Path Algorithm. 419-432
  

External Memory Algorithms

• Lars Arge, Gerth Stølting Brodal, Laura Toma:
  On External-Memory MST, SSSP, and Multi-way Planar Graph Separation. 433-447
  
• Lars Arge, Jakob Pagter:
  I/O-Space Trade-Offs. 448-461
  

Optimization

• Subhash Suri, Tuomas Sandholm, Priyank Ramesh Warkhede:
  Optimal Flow Aggregation. 462-475
  
• Tetsuo Asano, Tomomi Matsui, Takeshi Tokuyama:
  On the Complexities of the Optimal Rounding Problems of Sequences and Matrices. 476-489
  
• Shlomo Ahal, Yuri Rabinovich:
  On the Complexity of the Sub-permutation Problem. 490-503
  
• Peter Damaschke:
  Parallel Attribute-Efficient Learning of Monotone Boolean Functions. 504-512
  

Distributed Computing and Fault-Tolerance

• Kazuhisa Makino, Masafumi Yamashita, Tiko Kameda:
  Max- and Min-Neighborhood Monopolies. 513-526
  
• Andreas Björklund:
  Optimal Adaptive Fault Diagnosis of Hypercubes. 527-534
  
• Grzegorz Stachowiak:
  Fibonacci Correction Networks. 535-548
  
• Ferdinando Cicalese, Ugo Vaccaro, Daniele Mundici:
  Least Adaptive Optimal Search with Unreliable Tests. 549-562