8. SWAT 2002: Turku, Finland

Invited Speakers

• Torben Hagerup, Rajeev Raman:
  An Efficient Quasidictionary. 1-18
  
• Heikki Mannila:
  Combining Pattern Discovery and Probabilistic Modeling in Data Mining. 19
  

Scheduling

• Stephen Alstrup, Gerth Stølting Brodal, Inge Li Gørtz, Theis Rauhe:
  Time and Space Efficient Multi-method Dispatching. 20-29
  
• John E. Augustine, Steven S. Seiden:
  Linear Time Approximation Schemes for Vehicle Scheduling. 30-39
  
• Clint Hepner, Clifford Stein:
  Minimizing Makespan for the Lazy Bureaucrat Problem. 40-50
  
• Monaldo Mastrolilli:
  A PTAS for the Single Machine Scheduling Problem with Controllable Processing Times. 51-59
  

Computational Geometry

• Stephan Eidenbenz:
  Optimum Inapproximability Results for Finding Minimum Hidden Guard Sets in Polygons and Terrains. 60-68
  
• Partha P. Goswami, Sandip Das, Subhas C. Nandy:
  Simplex Range Searching and k Nearest Neighbors of a Line Segment in 2D. 69-79
  
• Christos Levcopoulos, Andrzej Lingas, Joseph S. B. Mitchell:
  Adaptive Algorithms for Constructing Convex Hulls and Triangulations of Polygonal Chains. 80-89
  
• Nissan Lev-Tov, David Peleg:
  Exact Algorithms and Approximation Schemes for Base Station Placement Problems. 90-99
  
• Zhongping Qin, Binhai Zhu:
  A Factor-2 Approximation for Labeling Points with Maximum Sliding Labels. 100-109
  
• Sasanka Roy, Partha P. Goswami, Sandip Das, Subhas C. Nandy:
  Optimal Algorithm for a Special Point-Labeling Problem. 110-120
  
• Peter Sanders, Berthold Vöcking:
  Random Arc Allocation and Applications. 121-130
  
• Micha Sharir, Shakhar Smorodinsky:
  On Neighbors in Geometric Permutations. 131-139
  

Graph Algorithms

• Geir Agnarsson, Peter Damaschke, Magnús M. Halldórsson:
  Powers of Geometric Intersection Graphs and Dispersion Algorithms. 140-149
  
• Jochen Alber, Michael R. Fellows, Rolf Niedermeier:
  Efficient Data Reduction for DOMINATING SET: A Linear Problem Kernel for the Planar Case. 150-159
  
• Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, Gerhard J. Woeginger:
  Planar Graph Coloring with Forbidden Subgraphs: Why Trees and Paths Are Dangerous. 160-169
  
• Miroslav Chlebík, Janka Chlebíková:
  Approximation Hardness of the Steiner Tree Problem on Graphs. 170-179
  
• John A. Ellis, Hongbing Fan, Michael R. Fellows:
  The Dominating Set Problem Is Fixed Parameter Tractable for Graphs of Bounded Genus. 180-189
  
• Harold N. Gabow, Seth Pettie:
  The Dynamic Vertex Minimum Problem and Its Application to Clustering-Type Approximation Algorithms. 190-199
  
• Alexander Golynski, Joseph Douglas Horton:
  A Polynomial Time Algorithm to Find the Minimum Cycle Basis of a Regular Matroid. 200-209
  
• Jochen Könemann, Yanjun Li, Ojas Parekh, Amitabh Sinha:
  Approximation Algorithms for Edge-Dilation k-Center Problems. 210-219
  
• Sarnath Ramnath:
  Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm. 220-229
  
• Ron Shamir, Dekel Tsur:
  Improved Algorithms for the Random Cluster Graph Model. 230-239
  
• San Skulrattanakulchai:
  Delta-List Vertex Coloring in Linear Time. 240-248
  

Robotics

• Erik D. Demaine, Alejandro López-Ortiz, J. Ian Munro:
  Robot Localization without Depth Perception. 249-259
  
• Alejandro López-Ortiz, Sven Schuierer:
  Online Parallel Heuristics and Robot Searching under the Competitive Framework. 260-269
  
• Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender, Joseph S. B. Mitchell:
  Analysis of Heuristics for the Freeze-Tag Problem. 270-279
  

Approximation Algorithms

• Esther M. Arkin, Refael Hassin, Shlomi Rubinstein, Maxim Sviridenko:
  Approximations for Maximum Transportation Problem with Permutable Supply Vector and Other Capacitated Star Packing Problems. 280-287
  
• Yossi Azar, Leah Epstein, Yossi Richter, Gerhard J. Woeginger:
  All-Norm Approximation Algorithms. 288-297
  
• Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski:
  Approximability of Dense Instances of NEAREST CODEWORD Problem. 298-307
  

Data Communication

• R. Sai Anand, Thomas Erlebach, Alexander Hall, Stamatis Stefanakos:
  Call Control with k Rejections. 308-317
  
• Guy Even, Guy Kortsarz, Wolfgang Slany:
  On Network Design Problems: Fixed Cost Flows and the Covering Steiner Problem. 318-327
  
• Jens S. Frederiksen, Kim S. Larsen:
  Packet Bundling. 328-337
  
• Anuj Puri, Stavros Tripakis:
  Algorithms for the Multi-constrained Routing Problem. 338-347
  

Computational Biology

• Juha Kärkkäinen:
  Computing the Threshold for q-Gram Filters. 348-357
  
• Itsik Pe'er, Ron Shamir, Roded Sharan:
  On the Generality of Phylogenies from Incomplete Directed Characters. 358-367
  

Data Storage and Manipulation

• Michael H. Albert, Mike D. Atkinson:
  Sorting with a Forklift. 368-377
  
• Hans L. Bodlaender, Fedor V. Fomin:
  Tree Decompositions with Small Cost. 378-387
  
• Hans L. Bodlaender, Udi Rotics:
  Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition. 388-397
  
• Jyrki Katajainen, Jeppe Nejsum Madsen:
  Performance Tuning an Algorithm for Compressing Relational Tables. 398-407
  
• Jyrki Katajainen, Tomi Pasanen:
  A Randomized In-Place Algorithm for Positioning the kth Element in a Multiset. 408-417
  
• Tony W. Lai:
  Paging on a RAM with Limited Resources. 418-427
  
• Alessandro Dal Palù, Enrico Pontelli, Desh Ranjan:
  An Optimal Algorithm for Finding NCA on Pure Pointer Machines. 428-438
  
• Eljas Soisalon-Soininen, Peter Widmayer:
  Amortized Complexity of Bulk Updates in AVL-Trees. 439-448