Algorithms – ESA 2006: 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006. Proceedings

Front Matter....Pages -
Origami, Linkages, and Polyhedra: Folding with Algorithms....Pages 1-1
Reliable and Efficient Geometric Computing....Pages 2-2
Some Computational Challenges in Today’s Bio-medicine....Pages 3-3
Kinetic Collision Detection for Convex Fat Objects....Pages 4-15
Dynamic Connectivity for Axis-Parallel Rectangles....Pages 16-27
Single Machine Precedence Constrained Scheduling Is a Vertex Cover Problem....Pages 28-39
Cooperative TSP....Pages 40-51
Fréchet Distance for Curves, Revisited....Pages 52-63
Resource Allocation in Bounded Degree Trees....Pages 64-75
Dynamic Algorithms for Graph Spanners....Pages 76-87
Latency Constrained Aggregation in Sensor Networks....Pages 88-99
Competitive Analysis of Flash-Memory Algorithms....Pages 100-111
Contention Resolution with Heterogeneous Job Sizes....Pages 112-123
Deciding Relaxed Two-Colorability—A Hardness Jump....Pages 124-135
Negative Examples for Sequential Importance Sampling of Binary Contingency Tables....Pages 136-147
Estimating Entropy over Data Streams....Pages 148-159
Necklaces, Convolutions, and X + Y ....Pages 160-171
Purely Functional Worst Case Constant Time Catenable Sorted Lists....Pages 172-183
Taxes for Linear Atomic Congestion Games....Pages 184-195
Spanners with Slack....Pages 196-207
Compressed Indexes for Approximate String Matching....Pages 208-219
Traversing the Machining Graph....Pages 220-231
Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Bimatrix Games....Pages 232-243
Distributed Almost Exact Approximations for Minor-Closed Families....Pages 244-255
Spectral Clustering by Recursive Partitioning....Pages 256-267
Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data....Pages 268-279
Dynamic Programming and Fast Matrix Multiplication....Pages 280-291
Near-Entropy Hotlink Assignments....Pages 292-303
Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods....Pages 304-314
Finding Total Unimodularity in Optimization Problems Solved by Linear Programs....Pages 315-326
Preemptive Online Scheduling: Optimal Algorithms for All Speeds....Pages 327-339
On the Complexity of the Multiplication Method for Monotone CNF/DNF Dualization....Pages 340-351
Lower and Upper Bounds on FIFO Buffer Management in QoS Switches....Pages 352-363
Graph Coloring with Rejection....Pages 364-375
A Doubling Dimension Threshold Θ(loglog n ) for Augmented Graph Navigability....Pages 376-386
Violator Spaces: Structure and Algorithms....Pages 387-398
Region-Restricted Clustering for Geographic Data Mining....Pages 399-410
An O ( n 3 (loglog n /log n ) 5/4 ) Time Algorithm for All Pairs Shortest Paths....Pages 411-417
Cheating by Men in the Gale-Shapley Stable Matching Algorithm....Pages 418-431
Approximating Almost All Instances of Max-Cut Within a Ratio Above the Håstad Threshold....Pages 432-443
Enumerating Spanning and Connected Subsets in Graphs and Matroids....Pages 444-455
Less Hashing, Same Performance: Building a Better Bloom Filter....Pages 456-467
A Unified Approach to Approximating Partial Covering Problems....Pages 468-479
Navigating Low-Dimensional and Hierarchical Population Networks....Pages 480-491
Popular Matchings in the Capacitated House Allocation Problem....Pages 492-503
Inner-Product Based Wavelet Synopses for Range-Sum Queries....Pages 504-515
Approximation in Preemptive Stochastic Online Scheduling....Pages 516-527
Greedy in Approximation Algorithms....Pages 528-539
I/O-Efficient Undirected Shortest Paths with Unbounded Edge Lengths....Pages 540-551
Stochastic Shortest Paths Via Quasi-convex Maximization....Pages 552-563
Path Hitting in Acyclic Graphs....Pages 564-575
Minimum Transversals in Posi-modular Systems....Pages 576-587
An LP-Designed Algorithm for Constraint Satisfaction....Pages 588-599
Approximate k -Steiner Forests Via the Lagrangian Relaxation Technique with Internal Preprocessing....Pages 600-611
Balancing Applied to Maximum Network Flow Problems....Pages 612-623
Out-of-Order Event Processing in Kinetic Data Structures....Pages 624-635
Kinetic Algorithms Via Self-adjusting Computation....Pages 636-647
Parallel Machine Scheduling Through Column Generation: Minimax Objective Functions....Pages 648-659
Reporting Flock Patterns....Pages 660-671
On Exact Algorithms for Treewidth....Pages 672-683
An Improved Construction for Counting Bloom Filters....Pages 684-695
An MINLP Solution Method for a Water Network Problem....Pages 696-707
Skewed Binary Search Trees....Pages 708-719
Algorithmic Aspects of Proportional Symbol Maps....Pages 720-731
Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?....Pages 732-743
Multiline Addressing by Network Flow....Pages 744-755
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression....Pages 756-767
The Price of Resiliency: A Case Study on Sorting with Memory Faults....Pages 768-779
How Branch Mispredictions Affect Quicksort....Pages 780-791
Robust, Generic and Efficient Construction of Envelopes of Surfaces in Three-Dimensional Spaces....Pages 792-803
Engineering Highway Hierarchies....Pages 804-816
Univariate Polynomial Real Root Isolation: Continued Fractions Revisited....Pages 817-828
Exact and Efficient Construction of Planar Minkowski Sums Using the Convolution Method....Pages 829-840
Back Matter....Pages -