14. ESA 2006:
Zurich,
Switzerland
Yossi Azar, Thomas Erlebach (Eds.):
Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings.
Lecture Notes in Computer Science 4168 Springer 2006, ISBN 3-540-38875-3 BibTeX
Invited Lectures
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
Electronic Edition (link) BibTeX
- Peyman Afshani, Timothy M. Chan:
Dynamic Connectivity for Axis-Parallel Rectangles.
16-27
Electronic Edition (link) BibTeX
- Christoph Ambühl, Monaldo Mastrolilli:
Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem.
28-39
Electronic Edition (link) BibTeX
- Amitai Armon, Adi Avidor, Oded Schwartz:
Cooperative TSP.
40-51
Electronic Edition (link) BibTeX
- Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, Carola Wenk:
Fréchet Distance for Curves, Revisited.
52-63
Electronic Edition (link) BibTeX
- Reuven Bar-Yehuda, Michael Beder, Yuval Cohen, Dror Rawitz:
Resource Allocation in Bounded Degree Trees.
64-75
Electronic Edition (link) BibTeX
- Surender Baswana:
Dynamic Algorithms for Graph Spanners.
76-87
Electronic Edition (link) BibTeX
- Luca Becchetti, Peter Korteweg, Alberto Marchetti-Spaccamela, Martin Skutella, Leen Stougie, Andrea Vitaletti:
Latency Constrained Aggregation in Sensor Networks.
88-99
Electronic Edition (link) BibTeX
- Avraham Ben-Aroya, Sivan Toledo:
Competitive Analysis of Flash-Memory Algorithms.
100-111
Electronic Edition (link) BibTeX
- Michael A. Bender, Jeremy T. Fineman, Seth Gilbert:
Contention Resolution with Heterogeneous Job Sizes.
112-123
Electronic Edition (link) BibTeX
- Robert Berke, Tibor Szabó:
Deciding Relaxed Two-Colorability - A Hardness Jump.
124-135
Electronic Edition (link) BibTeX
- Ivona Bezáková, Alistair Sinclair, Daniel Stefankovic, Eric Vigoda:
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables.
136-147
Electronic Edition (link) BibTeX
- Lakshminath Bhuvanagiri, Sumit Ganguly:
Estimating Entropy over Data Streams.
148-159
Electronic Edition (link) BibTeX
- 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
Electronic Edition (link) BibTeX
- Gerth Stølting Brodal, Christos Makris, Kostas Tsichlas:
Purely Functional Worst Case Constant Time Catenable Sorted Lists.
172-183
Electronic Edition (link) BibTeX
- Ioannis Caragiannis, Christos Kaklamanis, Panagiotis Kanellopoulos:
Taxes for Linear Atomic Congestion Games.
184-195
Electronic Edition (link) BibTeX
- Hubert T.-H. Chan, Michael Dinitz, Anupam Gupta:
Spanners with Slack.
196-207
Electronic Edition (link) BibTeX
- Ho-Leung Chan, Tak Wah Lam, Wing-Kin Sung, Siu-Lung Tam, Swee-Seong Wong:
Compressed Indexes for Approximate String Matching.
208-219
Electronic Edition (link) BibTeX
- Danny Z. Chen, Rudolf Fleischer, Jian Li, Haitao Wang, Hong Zhu:
Traversing the Machining Graph.
220-231
Electronic Edition (link) BibTeX
- Bruno Codenotti, Mauro Leoncini, Giovanni Resta:
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games.
232-243
Electronic Edition (link) BibTeX
- Andrzej Czygrinow, Michal Hanckowiak:
Distributed Almost Exact Approximations for Minor-Closed Families.
244-255
Electronic Edition (link) BibTeX
- Anirban Dasgupta, John E. Hopcroft, Ravi Kannan, Pradipta Prometheus Mitra:
Spectral Clustering by Recursive Partitioning.
256-267
Electronic Edition (link) BibTeX
- Brian C. Dean, Michel X. Goemans, Nicole Immorlica:
Finite Termination of "Augmenting Path" Algorithms in the Presence of Irrational Problem Data.
268-279
Electronic Edition (link) BibTeX
- Frederic Dorn:
Dynamic Programming and Fast Matrix Multiplication.
280-291
Electronic Edition (link) BibTeX
- Karim Douïeb, Stefan Langerman:
Near-Entropy Hotlink Assignments.
292-303
Electronic Edition (link) BibTeX
- Petros Drineas, Michael W. Mahoney, S. Muthukrishnan:
Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods.
304-314
Electronic Edition (link) BibTeX
- Christoph Dürr, Mathilde Hurand:
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs.
315-326
Electronic Edition (link) BibTeX
- Tomás Ebenlendr, Wojciech Jawor, Jiri Sgall:
Preemptive Online Scheduling: Optimal Algorithms for All Speeds.
327-339
Electronic Edition (link) BibTeX
- Khaled M. Elbassioni:
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization.
340-351
Electronic Edition (link) BibTeX
- Matthias Englert, Matthias Westermann:
Lower and Upper Bounds on FIFO Buffer Management in QoS Switches.
352-363
Electronic Edition (link) BibTeX
- Leah Epstein, Asaf Levin, Gerhard J. Woeginger:
Graph Coloring with Rejection.
364-375
Electronic Edition (link) BibTeX
- Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker:
A Doubling Dimension Threshold Theta(loglogn) for Augmented Graph Navigability.
376-386
Electronic Edition (link) BibTeX
- Bernd Gärtner, Jirí Matousek, Leo Rüst, Petr Skovron:
Violator Spaces: Structure and Algorithms.
387-398
Electronic Edition (link) BibTeX
- Joachim Gudmundsson, Marc J. van Kreveld, Giri Narasimhan:
Region-Restricted Clustering for Geographic Data Mining.
399-410
Electronic Edition (link) BibTeX
- Yijie Han:
An O(n3 (loglogn/logn)5/4) Time Algorithm for All Pairs Shortest Paths.
411-417
Electronic Edition (link) BibTeX
- Chien-Chung Huang:
Cheating by Men in the Gale-Shapley Stable Matching Algorithm.
418-431
Electronic Edition (link) BibTeX
- 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
Electronic Edition (link) BibTeX
- Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino:
Enumerating Spanning and Connected Subsets in Graphs and Matroids.
444-455
Electronic Edition (link) BibTeX
- Adam Kirsch, Michael Mitzenmacher:
Less Hashing, Same Performance: Building a Better Bloom Filter.
456-467
Electronic Edition (link) BibTeX
- Jochen Könemann, Ojas Parekh, Danny Segev:
A Unified Approach to Approximating Partial Covering Problems.
468-479
Electronic Edition (link) BibTeX
- Ravi Kumar, David Liben-Nowell, Andrew Tomkins:
Navigating Low-Dimensional and Hierarchical Population Networks.
480-491
Electronic Edition (link) BibTeX
- David Manlove, Colin T. S. Sng:
Popular Matchings in the Capacitated House Allocation Problem.
492-503
Electronic Edition (link) BibTeX
- Yossi Matias, Daniel Urieli:
Inner-Product Based Wavelet Synopses for Range-Sum Queries.
504-515
Electronic Edition (link) BibTeX
- Nicole Megow, Tjark Vredeveld:
Approximation in Preemptive Stochastic Online Scheduling.
516-527
Electronic Edition (link) BibTeX
- Julián Mestre:
Greedy in Approximation Algorithms.
528-539
Electronic Edition (link) BibTeX
- Ulrich Meyer, Norbert Zeh:
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths.
540-551
Electronic Edition (link) BibTeX
- Evdokia Nikolova, Jonathan A. Kelner, Matthew Brand, Michael Mitzenmacher:
Stochastic Shortest Paths Via Quasi-convex Maximization.
552-563
Electronic Edition (link) BibTeX
- Ojas Parekh, Danny Segev:
Path Hitting in Acyclic Graphs.
564-575
Electronic Edition (link) BibTeX
- Mariko Sakashita, Kazuhisa Makino, Hiroshi Nagamochi, Satoru Fujishige:
Minimum Transversals in Posi-modular Systems.
576-587
Electronic Edition (link) BibTeX
- Alexander D. Scott, Gregory B. Sorkin:
An LP-Designed Algorithm for Constraint Satisfaction.
588-599
Electronic Edition (link) BibTeX
- Danny Segev, Gil Segev:
Approximate k-Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing.
600-611
Electronic Edition (link) BibTeX
- Robert Endre Tarjan, Julie Ward, Bin Zhang, Yunhong Zhou, Jia Mao:
Balancing Applied to Maximum Network Flow Problems.
612-623
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX
- Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Jorge L. Vittes:
Kinetic Algorithms Via Self-adjusting Computation.
636-647
Electronic Edition (link) BibTeX
- Marjan van den Akker, J. A. Hoogeveen, Jules W. van Kempen:
Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions.
648-659
Electronic Edition (link) BibTeX
- Marc Benkert, Joachim Gudmundsson, Florian Hübner, Thomas Wolle:
Reporting Flock Patterns.
660-671
Electronic Edition (link) BibTeX
- Hans L. Bodlaender, Fedor V. Fomin, Arie M. C. A. Koster, Dieter Kratsch, Dimitrios M. Thilikos:
On Exact Algorithms for Treewidth.
672-683
Electronic Edition (link) BibTeX
- Flavio Bonomi, Michael Mitzenmacher, Rina Panigrahy, Sushil Singh, George Varghese:
An Improved Construction for Counting Bloom Filters.
684-695
Electronic Edition (link) BibTeX
- Cristiana Bragalli, Claudia D'Ambrosio, Jon Lee, Andrea Lodi, Paolo Toth:
An MINLP Solution Method for a Water Network Problem.
696-707
Electronic Edition (link) BibTeX
- Gerth Stølting Brodal, Gabriel Moruz:
Skewed Binary Search Trees.
708-719
Electronic Edition (link) BibTeX
- Sergio Cabello, Herman J. Haverkort, Marc J. van Kreveld, Bettina Speckmann:
Algorithmic Aspects of Proportional Symbol Maps.
720-731
Electronic Edition (link) BibTeX
- Camil Demetrescu, Pompeo Faruolo, Giuseppe F. Italiano, Mikkel Thorup:
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?
732-743
Electronic Edition (link) BibTeX
- Friedrich Eisenbrand, Andreas Karrenbauer, Martin Skutella, Chihao Xu:
Multiline Addressing by Network Flow.
744-755
Electronic Edition (link) BibTeX
- Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini:
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression.
756-767
Electronic Edition (link) BibTeX
- Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano:
The Price of Resiliency: A Case Study on Sorting with Memory Faults.
768-779
Electronic Edition (link) BibTeX
- Kanela Kaligosi, Peter Sanders:
How Branch Mispredictions Affect Quicksort.
780-791
Electronic Edition (link) BibTeX
- Michal Meyerovitch:
Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces.
792-803
Electronic Edition (link) BibTeX
- Peter Sanders, Dominik Schultes:
Engineering Highway Hierarchies.
804-816
Electronic Edition (link) BibTeX
- Elias P. Tsigaridas, Ioannis Z. Emiris:
Univariate Polynomial Real Root Isolation: Continued Fractions Revisited.
817-828
Electronic Edition (link) BibTeX
- Ron Wein:
Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method.
829-840
Electronic Edition (link) BibTeX
Copyright © Fri May 16 16:22:01 2008
by Michael Ley (ley@uni-trier.de)
