9. ESA 2001: Aarhus, Denmark

Invited Talks

• Lars Arge:
  External Memory Data Structures. 1-29
  
• Susanne Albers:
  Some Algorithmic Problems in Large Networks. 30-32
  
• Uri Zwick:
  Exact and Approximate Distances in Graphs - A Survey. 33-48
  

Caching and Prefetching

• Alexander Gaysinsky, Alon Itai, Hadas Shachnai:
  Strongly Competitive Algorithms for Caching with Pipelined Prefetching. 49-61
  
• David A. Hutchinson, Peter Sanders, Jeffrey Scott Vitter:
  Duality between Prefetching and Queued Writing with Parallel Disks. 62-73
  

Online Algorithms

• Sven Oliver Krumke, Willem de Paepe, Jörg Rambau, Leen Stougie:
  Online Bin Coloring. 74-85
  
• Steven S. Seiden:
  A General Decomposition Theorem for the k-Server Problem. 86-97
  
• János Csirik, Csanád Imreh, John Noga, Steven S. Seiden, Gerhard J. Woeginger:
  Buying a Constant Competitive Ratio for Paging. 98-108
  

Data Structures I

• Martin Dietzfelbinger, Torben Hagerup:
  Simple Minimal Perfect Hashing in Less Space. 109-120
  
• Rasmus Pagh, Flemming Friche Rodler:
  Cuckoo Hashing. 121-133
  

Optimization and Approximation

• Meinolf Sellmann, Torsten Fahle:
  Coupling Variable Fixing Algorithms for the Automatic Recording Problem. 134-145
  
• Renaud Lepère, Denis Trystram, Gerhard J. Woeginger:
  Approximation Algorithms for Scheduling Malleable Tasks under Precedence Constraints. 146-157
  
• Bjarni V. Halldórsson, Magnús M. Halldórsson, R. Ravi:
  On the Approximability of the Minimum Test Collection Problem. 158-169
  

Sequences

• Roman M. Kolpakov, Gregory Kucherov:
  Finding Approximate Repetitions under Hamming Distance. 170-181
  
• Giuseppe Lancia, Vineet Bafna, Sorin Istrail, Ross Lippert, Russell Schwartz:
  SNPs Problems, Complexity, and Algorithms. 182-193
  

Scheduling

• Eric Angel, Evripidis Bampis, Alexander Kononov:
  A FPTAS for Approximating the Unrelated Parallel Machines Scheduling Problem with Costs. 194-205
  
• Aleksei V. Fishkin, Klaus Jansen, Monaldo Mastrolilli:
  Grouping Techniques for Scheduling Problems: Simpler and Faster. 206-217
  
• Yoshiyuki Karuno, Hiroshi Nagamochi:
  A 2-Approximation Algorithm for the Multi-vehicle Scheduling Problem on a Path with Release and Handling Times. 218-229
  

Shortest Path

• Andrew V. Goldberg:
  A Simple Shortest Path Algorithm with Linear Average Time. 230-241
  
• Kurt Mehlhorn, Guido Schäfer:
  A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms. 242-253
  

Geometry I

• Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt:
  A Separation Bound for Real Algebraic Expressions. 254-265
  
• Artur Czumaj, Christian Sohler:
  Property Testing with Geometric Queries. 266-277
  
• Manuel Abellanas, Ferran Hurtado, Christian Icking, Rolf Klein, Elmar Langetepe, Lihong Ma, Belén Palop, Vera Sacristan:
  Smallest Color-Spanning Objects. 278-289
  

Data Structures II

• Jaikumar Radhakrishnan, Venkatesh Raman, S. Srinivasa Rao:
  Explicit Deterministic Constructions for Membership in the Bitprobe Model. 290-299
  
• Rasmus Pagh, Flemming Friche Rodler:
  Lossy Dictionaries. 300-311
  

Geometry II

• Bernard Chazelle, Olivier Devillers, Ferran Hurtado, Mercè Mora, Vera Sacristan, Monique Teillaud:
  Splitting a Delaunay Triangulation in Linear Time. 312-320
  
• Annette Ebbers-Baumann, Rolf Klein, Elmar Langetepe, Andrzej Lingas:
  A Fast Algorithm for Approximating the Detour of a Polygonal Chain. 321-332
  
• Stephan Eidenbenz, Peter Widmayer:
  An Approximation Algorithm for MINIMUM CONVEX COVER with Logarithmic Performance Guarantee. 333-344
  

Distributed Algorithms

• Andrzej Czygrinow, Michal Hanckowiak, Michal Karonski:
  Distributed O(Delta log(n))-Edge-Coloring Algorithm. 345-355
  
• John R. Douceur, Roger Wattenhofer:
  Modeling Replica Placement in a Distributed File System: Narrowing the Gap between Analysis and Simulation. 356-367
  

Graph Algorithms

• Markus Bläser, Bodo Siebert:
  Computing Cycle Covers without Short Cycles. 368-379
  
• Dimitrios M. Thilikos, Maria J. Serna, Hans L. Bodlaender:
  A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth. 380-390
  
• Norbert Sensen:
  Lower Bounds and Exact Algorithms for the Graph Partitioning Problem Using Multicommodity Flows. 391-403
  

Pricing

• Karhan Akcoglu, Ming-Yang Kao, Shuba V. Raghavan:
  Fast Pricing of European Asian Options with Provable Accuracy: Single-Stock and Basket Options. 404-415
  
• Andrew V. Goldberg, Jason D. Hartline:
  Competitive Auctions for Multiple Digital Goods. 416-427
  

Broadcasting and Multicasting

• Stefan Langerman, Sachin Lodha, Rahul Shah:
  Algorithms for Efficient Filtering in Content-Based Multicast. 428-439
  
• Pierre Fraigniaud:
  Approximation Algorithms for Minimum-Time Broadcast under the Vertex-Disjoint Paths Mode. 440-451
  
• Andrea E. F. Clementi, Angelo Monti, Riccardo Silvestri:
  Round Robin Is Optimal for Fault-Tolerant Broadcasting on Wireless Networks. 452-463
  

Graph Labeling and Graph Drawing

• Jirí Fiala, Aleksei V. Fishkin, Fedor V. Fomin:
  Online and Offline Distance Constrained Labeling of Disk Graphs. 464-475
  
• Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, David Peleg:
  Approximate Distance Labeling Schemes. 476-487
  
• Vida Dujmovic, Michael R. Fellows, Michael T. Hallett, Matthew Kitching, Giuseppe Liotta, Catherine McCartin, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Matthew Suderman, Sue Whitesides, David R. Wood:
  On the Parameterized Complexity of Layered Graph Drawing. 488-499
  

Graphs

• Colin Cooper, Alan M. Frieze:
  A General Model of Undirected Web Graphs. 500-511
  
• Alberto Caprara, Alessandro Panconesi, Romeo Rizzi:
  Packing Cycles and Cuts in Undirected Graphs. 512-523
  
• Michele Zito:
  Greedy Algorithms for Minimisation Problems in Random Regular Graphs. 524-536