14. ESA 2006: Zurich, Switzerland

Invited Lectures

• Erik D. Demaine:
  Origami, Linkages, and Polyhedra: Folding with Algorithms. 1
  
• Kurt Mehlhorn:
  Reliable and Efficient Geometric Computing. 2
  
• Ron Shamir:
  Some Computational Challenges in Today's Bio-medicine. 3
  

Contributed Papers: Design and Analysis Track

• Mohammad Ali Abam, Mark de Berg, Sheung-Hung Poon, Bettina Speckmann:
  Kinetic Collision Detection for Convex Fat Objects. 4-15
  
• Peyman Afshani, Timothy M. Chan:
  Dynamic Connectivity for Axis-Parallel Rectangles. 16-27
  
• Christoph Ambühl, Monaldo Mastrolilli:
  Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem. 28-39
  
• Amitai Armon, Adi Avidor, Oded Schwartz:
  Cooperative TSP. 40-51
  
• Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk:
  Fréchet Distance for Curves, Revisited. 52-63
  
• Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz:
  Resource Allocation in Bounded Degree Trees. 64-75
  
• Surender Baswana:
  Dynamic Algorithms for Graph Spanners. 76-87
  
• Luca Becchetti, Peter Korteweg, Alberto Marchetti-Spaccamela, Martin Skutella, Leen Stougie, Andrea Vitaletti:
  Latency Constrained Aggregation in Sensor Networks. 88-99
  
• Avraham Ben-Aroya, Sivan Toledo:
  Competitive Analysis of Flash-Memory Algorithms. 100-111
  
• Michael A. Bender, Jeremy T. Fineman, Seth Gilbert:
  Contention Resolution with Heterogeneous Job Sizes. 112-123
  
• Robert Berke, Tibor Szabó:
  Deciding Relaxed Two-Colorability - A Hardness Jump. 124-135
  
• Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda:
  Negative Examples for Sequential Importance Sampling of Binary Contingency Tables. 136-147
  
• Lakshminath Bhuvanagiri, Sumit Ganguly:
  Estimating Entropy over Data Streams. 148-159
  
• David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian:
  Necklaces, Convolutions, and X + Y. 160-171
  
• Gerth Stølting Brodal, Christos Makris, Kostas Tsichlas:
  Purely Functional Worst Case Constant Time Catenable Sorted Lists. 172-183
  
• Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
  Taxes for Linear Atomic Congestion Games. 184-195
  
• Hubert T.-H. Chan, Michael Dinitz, Anupam Gupta:
  Spanners with Slack. 196-207
  
• Ho-Leung Chan, Tak Wah Lam, Wing-Kin Sung, Siu-Lung Tam, Swee-Seong Wong:
  Compressed Indexes for Approximate String Matching. 208-219
  
• Danny Z. Chen, Rudolf Fleischer, Jian Li, Haitao Wang, Hong Zhu:
  Traversing the Machining Graph. 220-231
  
• Bruno Codenotti, Mauro Leoncini, Giovanni Resta:
  Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games. 232-243
  
• Andrzej Czygrinow, Michal Hanckowiak:
  Distributed Almost Exact Approximations for Minor-Closed Families. 244-255
  
• Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra:
  Spectral Clustering by Recursive Partitioning. 256-267
  
• Brian C. Dean, Michel X. Goemans, Nicole Immorlica:
  Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data. 268-279
  
• Frederic Dorn:
  Dynamic Programming and Fast Matrix Multiplication. 280-291
  
• Karim Douïeb, Stefan Langerman:
  Near-Entropy Hotlink Assignments. 292-303
  
• Petros Drineas, Michael W. Mahoney, S. Muthukrishnan:
  Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods. 304-314
  
• Christoph Dürr, Mathilde Hurand:
  Finding Total Unimodularity in Optimization Problems Solved by Linear Programs. 315-326
  
• Tomás Ebenlendr, Wojciech Jawor, Jiri Sgall:
  Preemptive Online Scheduling: Optimal Algorithms for All Speeds. 327-339
  
• Khaled M. Elbassioni:
  On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization. 340-351
  
• Matthias Englert, Matthias Westermann:
  Lower and Upper Bounds on FIFO Buffer Management in QoS Switches. 352-363
  
• Leah Epstein, Asaf Levin, Gerhard J. Woeginger:
  Graph Coloring with Rejection. 364-375
  
• Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker:
  A Doubling Dimension Threshold Theta(loglogn) for Augmented Graph Navigability. 376-386
  
• Bernd Gärtner, Jirí Matousek, Leo Rüst, Petr Skovron:
  Violator Spaces: Structure and Algorithms. 387-398
  
• Joachim Gudmundsson, Marc J. van Kreveld, Giri Narasimhan:
  Region-Restricted Clustering for Geographic Data Mining. 399-410
  
• Yijie Han:
  An O(n³ (loglogn/logn)^5/4) Time Algorithm for All Pairs Shortest Paths. 411-417
  
• Chien-Chung Huang:
  Cheating by Men in the Gale-Shapley Stable Matching Algorithm. 418-431
  
• Alexis C. Kaporis, Lefteris M. Kirousis, Elias C. Stavropoulos:
  Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold. 432-443
  
• Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino:
  Enumerating Spanning and Connected Subsets in Graphs and Matroids. 444-455
  
• Adam Kirsch, Michael Mitzenmacher:
  Less Hashing, Same Performance: Building a Better Bloom Filter. 456-467
  
• Jochen Könemann, Ojas Parekh, Danny Segev:
  A Unified Approach to Approximating Partial Covering Problems. 468-479
  
• Ravi Kumar, David Liben-Nowell, Andrew Tomkins:
  Navigating Low-Dimensional and Hierarchical Population Networks. 480-491
  
• David Manlove, Colin T. S. Sng:
  Popular Matchings in the Capacitated House Allocation Problem. 492-503
  
• Yossi Matias, Daniel Urieli:
  Inner-Product Based Wavelet Synopses for Range-Sum Queries. 504-515
  
• Nicole Megow, Tjark Vredeveld:
  Approximation in Preemptive Stochastic Online Scheduling. 516-527
  
• Julián Mestre:
  Greedy in Approximation Algorithms. 528-539
  
• Ulrich Meyer, Norbert Zeh:
  I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths. 540-551
  
• Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher:
  Stochastic Shortest Paths Via Quasi-convex Maximization. 552-563
  
• Ojas Parekh, Danny Segev:
  Path Hitting in Acyclic Graphs. 564-575
  
• Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige:
  Minimum Transversals in Posi-modular Systems. 576-587
  
• Alexander D. Scott, Gregory B. Sorkin:
  An LP-Designed Algorithm for Constraint Satisfaction. 588-599
  
• Danny Segev, Gil Segev:
  Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing. 600-611
  
• Robert Endre Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, Jia Mao:
  Balancing Applied to Maximum Network Flow Problems. 612-623
  

Contributed Papers: Engineering and Applications Track

• Mohammad Ali Abam, Pankaj K. Agarwal, Mark de Berg, Hai Yu:
  Out-of-Order Event Processing in Kinetic Data Structures. 624-635
  
• Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes:
  Kinetic Algorithms Via Self-adjusting Computation. 636-647
  
• Marjan van den Akker, J. A. Hoogeveen, Jules W. van Kempen:
  Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions. 648-659
  
• Marc Benkert, Joachim Gudmundsson, Florian Hübner, Thomas Wolle:
  Reporting Flock Patterns. 660-671
  
• Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos:
  On Exact Algorithms for Treewidth. 672-683
  
• Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese:
  An Improved Construction for Counting Bloom Filters. 684-695
  
• Cristiana Bragalli, Claudia D'Ambrosio, Jon Lee, Andrea Lodi, Paolo Toth:
  An MINLP Solution Method for a Water Network Problem. 696-707
  
• Gerth Stølting Brodal, Gabriel Moruz:
  Skewed Binary Search Trees. 708-719
  
• Sergio Cabello, Herman J. Haverkort, Marc J. van Kreveld, Bettina Speckmann:
  Algorithmic Aspects of Proportional Symbol Maps. 720-731
  
• Camil Demetrescu, Pompeo Faruolo, Giuseppe F. Italiano, Mikkel Thorup:
  Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths? 732-743
  
• Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella, Chihao Xu:
  Multiline Addressing by Network Flow. 744-755
  
• Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini:
  The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression. 756-767
  
• Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano:
  The Price of Resiliency: A Case Study on Sorting with Memory Faults. 768-779
  
• Kanela Kaligosi, Peter Sanders:
  How Branch Mispredictions Affect Quicksort. 780-791
  
• Michal Meyerovitch:
  Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces. 792-803
  
• Peter Sanders, Dominik Schultes:
  Engineering Highway Hierarchies. 804-816
  
• Elias P. Tsigaridas, Ioannis Z. Emiris:
  Univariate Polynomial Real Root Isolation: Continued Fractions Revisited. 817-828
  
• Ron Wein:
  Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method. 829-840