12. ESA 2004: Bergen, Norway

Invited Lectures

• Michael R. Fellows:
  A Survey of FPT Algorithm Design Techniques with an Emphasis on Recent Advances and Connections to Practical Computing. 1-2
  
• Monika Rauch Henzinger:
  Algorithmic Aspects of Web Search Engines. 3
  

Design and Analysis Track

• Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Hai Yu:
  Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects. 4-15
  
• Amihood Amir, Estrella Eisenberg, Ely Porat:
  Swap and Mismatch Edit Distance. 16-27
  
• Elliot Anshelevich, Lisa Zhang:
  Path Decomposition Under a New Cost Measure with Applications to Optical Network Design. 28-39
  
• Lars Arge, Vasilis Samoladas, Ke Yi:
  Optimal External Memory Planar Point Enclosure. 40-52
  
• Yossi Azar, Arik Litichevskey:
  Maximizing Throughput in Multi-queue Switches. 53-64
  
• Yossi Azar, Yossi Richter:
  An Improved Algorithm for CIOQ Switches. 65-76
  
• Vikas Bansal, Friedhelm Meyer auf der Heide, Christian Sohler:
  Labeling Smart Dust. 77-88
  
• Yair Bartal:
  Graph Decomposition Lemmas and Their Role in Metric Embedding Methods. 89-97
  
• Luca Becchetti:
  Modeling Locality: A Probabilistic Analysis of LRU and FWF. 98-109
  
• Ankur Bhargava, S. Rao Kosaraju:
  An Algorithm for Computing DNA Walks. 110-121
  
• Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich:
  Algorithms for Generating Minimal Blockers of Perfect Matchings in Bipartite Graphs and Related Problems. 122-133
  
• Costas Busch, Malik Magdon-Ismail, Marios Mavronicolas, Paul G. Spirakis:
  Direct Routing: Algorithms and Complexity. 134-145
  
• Douglas E. Carroll, Ashish Goel:
  Lower Bounds for Embedding into Distributions over Excluded Minor Graph Families. 146-156
  
• Hubert Y. Chan:
  A Parameterized Algorithm for Upward Planarity Testing. 157-168
  
• Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao:
  Fisher Equilibrium Price with a Class of Concave Utility Functions. 169-179
  
• Joseph Cheriyan, Mohammad R. Salavatipour:
  Hardness and Approximation Results for Packing Steiner Trees. 180-191
  
• Miroslav Chlebík, Janka Chlebíková:
  Approximation Hardness of Dominating Set Problems. 192-203
  
• Marek Chrobak, Wojciech Jawor, Jiri Sgall, Tomás Tichý:
  Improved Online Algorithms for Buffer Management in QoS Switches. 204-215
  
• Rami Cohen, Dror Rawitz, Danny Raz:
  Time Dependent Multi Scheduling of Multicast. 216-227
  
• Reuven Cohen, David Peleg:
  Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems. 228-239
  
• Richard Cole, David C. Kandathil:
  The Average Case Analysis of Partition Sorts. 240-251
  
• Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymanska:
  A Fast Distributed Algorithm for Approximating the Maximum Matching. 252-263
  
• Valentina Damerow, Christian Sohler:
  Extreme Points Under Random Noise. 264-274
  
• Josep Díaz, Maria J. Serna, Dimitrios M. Thilikos:
  Fixed Parameter Algorithms for Counting and Deciding Bounded Restrictive List H-Colorings. 275-286
  
• Leah Epstein, Rob van Stee:
  On Variable-Sized Multidimensional Packing. 287-298
  
• Zsolt Fekete, Tibor Jordán, Walter Whiteley:
  An Inductive Construction for Plane Laman Graphs via Vertex Splitting. 299-310
  
• Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos, Sue Whitesides:
  Faster Fixed-Parameter Tractable Algorithms for Matching and Packing Problems. 311-322
  
• Simon Fischer, Berthold Vöcking:
  On the Evolution of Selfish Routing. 323-334
  
• Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
  Competitive Online Approximation of the Optimal Search Ratio. 335-346
  
• Dimitris Fotakis:
  Incremental Algorithms for Facility Location and k-Median. 347-358
  
• Travis Gagie:
  Dynamic Shannon Coding. 359-370
  
• Naveen Garg, Rohit Khandekar:
  Fractional Covering with Upper Bounds on the Variables: Solving LPs with Negative Entries. 371-382
  
• Rica Gonen:
  Negotiation-Range Mechanisms: Coalition-Resistant Markets. 383-394
  
• Refael Hassin, Asaf Levin:
  Approximation Algorithms for Quickest Spanning Tree Problems. 395-402
  
• Refael Hassin, Shlomi Rubinstein:
  An Approximation Algorithm for Maximum Triangle Packing. 403-413
  
• Carmit Hazay, Moshe Lewenstein, Dina Sokol:
  Approximate Parameterized Matching. 414-425
  
• Sofia Kovaleva, Frits C. R. Spieksma:
  Approximation of Rectangle Stabbing and Interval Stabbing Problems. 426-435
  
• Lukasz Kowalik:
  Fast 3-Coloring Triangle-Free Planar Graphs. 436-447
  
• Marc J. van Kreveld, A. Frank van der Stappen:
  Approximate Unions of Lines and Minkowski Sums. 448-459
  
• Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer:
  Radio Network Clustering from Scratch. 460-471
  
• Raghav Kulkarni, Meena Mahajan:
  Seeking a Vertex of the Planar Matching Polytope in NC. 472-483
  
• Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa:
  Equivalence of Search Capability Among Mobile Guards with Various Visibilities. 484-495
  
• Junning Liu, Micah Adler:
  Load Balancing in Hypercubic Distributed Hash Tables with Heterogeneous Processors. 496-507
  
• Varun S. Malhotra:
  On the Stability of Multiple Partner Stable Marriages with Ties. 508-519
  
• Maren Martens, Martin Skutella:
  Flows on Few Paths: Algorithms and Lower Bounds. 520-531
  
• Marcin Mucha, Piotr Sankowski:
  Maximum Matchings in Planar Graphs via Gaussian Elimination. 532-543
  
• Michael Nüsken, Martin Ziegler:
  Fast Multipoint Evaluation of Bivariate Polynomials. 544-555
  
• Anna Pagh, Rasmus Pagh, Mikkel Thorup:
  On Adaptive Integer Sorting. 556-579
  
• Eric Rémila:
  Tiling a Polygon with Two Kinds of Rectangles. 568-579
  
• Liam Roditty, Uri Zwick:
  On Dynamic Shortest Paths Problems. 580-591
  
• Milan Ruzic:
  Uniform Algorithms for Deterministic Construction of Efficient Dictionaries. 592-603
  
• Raphael Yuster, Uri Zwick:
  Fast Sparse Matrix Multiplication. 604-615
  

Engineering and Applications Track

• René Beier, Berthold Vöcking:
  An Experimental Study of Random Knapsack Problems. 616-627
  
• Hans L. Bodlaender, Arie M. C. A. Koster, Thomas Wolle:
  Contraction and Treewidth Lower Bounds. 628-639
  
• Robert Elsässer, Burkhard Monien, Stefan Schamberger:
  Load Balancing of Indivisible Unit Size Tokens in Dynamic and Heterogeneous Networks. 640-651
  
• Ioannis Z. Emiris, Elias P. Tsigaridas:
  Comparing Real Algebraic Numbers of Small Degree. 652-663
  
• Efi Fogel, Ron Wein, Dan Halperin:
  Code Flexibility and Program Efficiency by Genericity: Improving Cgal's Arrangements. 664-676
  
• Loukas Georgiadis, Renato Fonseca F. Werneck, Robert Endre Tarjan, Spyridon Triantafyllis, David I. August:
  Finding Dominators in Practice. 677-688
  
• Leana Golubchik, Samir Khuller, Yoo Ah Kim, Svetlana Shargorodskaya, Yung-Chun (Justin) Wan:
  Data Migration on Parallel Disks. 689-701
  
• Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, Chee-Keng Yap:
  Classroom Examples of Robustness Problems in Geometric Computations. 702-713
  
• Pok-Son Kim, Arne Kutzner:
  Stable Minimum Storage Merging by Symmetric Comparisons. 714-723
  
• Marc J. van Kreveld, Bettina Speckmann:
  On Rectangular Cartograms. 724-735
  
• Andreas Larsson, Anders Gidenstam, Phuong Hoai Ha, Marina Papatriantafilou, Philippas Tsigas:
  Multi-word Atomic Read/Write Registers on Multiprocessor Systems. 736-748
  
• Ulf Lorenz:
  Beyond Optimal Play in Two-Person-Zerosum Games. 749-759
  
• Steffen Mecke, Dorothea Wagner:
  Solving Geometric Covering Problems by Data Reduction. 760-771
  
• Marco Pellegrini, Giordano Fusco:
  Efficient IP Table Lookup via Adaptive Stratified Trees with Selective Reconstructions. 772-783
  
• Peter Sanders, Sebastian Winkel:
  Super Scalar Sample Sort. 784-796
  
• Mikkel Sigurd, Martin Zachariasen:
  Construction of Minimum-Weight Spanners. 797-808
  
• Mirela Tanase, Remco C. Veltkamp:
  A Straight Skeleton Approximating the Medial Axis. 809-821
  
• George Tsaggouris, Christos D. Zaroliagis:
  Non-additive Shortest Paths. 822-834