Algorithms - ESA 2008: 16th Annual European Symposium, Karlsruhe, Germany, September 15-17, 2008. Proceedings

Front Matter....Pages -
Flexible Path Planning Using Corridor Maps....Pages 1-12
A Bridging Model for Multi-core Computing....Pages 13-28
Robust Kinetic Convex Hulls in 3D....Pages 29-40
On Dominance Reporting in 3D....Pages 41-51
Stabbing Convex Polygons with a Segment or a Polygon....Pages 52-63
An Efficient Algorithm for 2D Euclidean 2-Center with Outliers....Pages 64-75
A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry....Pages 76-87
Cache-Oblivious Red-Blue Line Segment Intersection....Pages 88-99
The Complexity of Bisectors and Voronoi Diagrams on Realistic Terrains....Pages 100-111
Space-Time Tradeoffs for Proximity Searching in Doubling Spaces....Pages 112-123
A Scaling Algorithm for the Maximum Node-Capacitated Multiflow Problem....Pages 124-135
Linear Time Planarity Testing and Embedding of Strongly Connected Cyclic Level Graphs....Pages 136-147
Straight Skeletons of Three-Dimensional Polyhedra....Pages 148-160
Randomized Competitive Analysis for Two-Server Problems....Pages 161-172
Decompositions and Boundary Coverings of Non-convex Fat Polyhedra....Pages 173-184
Approximating Multi-criteria Max-TSP....Pages 185-197
An Integer Programming Algorithm for Routing Optimization in IP Networks....Pages 198-209
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling....Pages 210-221
Tight Bounds and a Fast FPT Algorithm for Directed Max-Leaf Spanning Tree....Pages 222-233
Engineering Tree Labeling Schemes: A Case Study on Least Common Ancestors....Pages 234-245
A Practical Quicksort Algorithm for Graphics Processors....Pages 246-258
Bloomier Filters: A Second Look....Pages 259-270
Coupled Path Planning, Region Optimization, and Applications in Intensity-Modulated Radiation Therapy....Pages 271-283
A New Approach to Exact Crossing Minimization....Pages 284-296
A Characterization of 2-Player Mechanisms for Scheduling....Pages 297-307
A Local-Search 2-Approximation for 2-Correlation-Clustering....Pages 308-319
The Alcuin Number of a Graph....Pages 320-331
Time-Dependent SHARC-Routing....Pages 332-343
Detecting Regular Visit Patterns....Pages 344-355
Improved Approximation Algorithms for Relay Placement....Pages 356-367
Selfish Bin Packing....Pages 368-380
Improved Randomized Results for That Interval Selection Problem....Pages 381-392
Succinct Representations of Arbitrary Graphs....Pages 393-404
Edge Coloring and Decompositions of Weighted Graphs....Pages 405-416
The Complexity of Sorting with Networks of Stacks and Queues....Pages 417-429
Faster Steiner Tree Computation in Polynomial-Space....Pages 430-441
Fitting a Step Function to a Point Set....Pages 442-453
Faster Swap Edge Computation in Minimum Diameter Spanning Trees....Pages 454-465
The Partial Augment–Relabel Algorithm for the Maximum Flow Problem....Pages 466-477
An Optimal Dynamic Spanner for Doubling Metric Spaces....Pages 478-489
RFQ: Redemptive Fair Queuing....Pages 490-502
Range Medians....Pages 503-514
Locality and Bounding-Box Quality of Two-Dimensional Space-Filling Curves....Pages 515-527
Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison....Pages 528-539
On the Complexity of Optimal Hotlink Assignment....Pages 540-552
Oblivious Randomized Direct Search for Real-Parameter Optimization....Pages 553-564
Path Minima in Incremental Unrooted Trees....Pages 565-576
Improved Competitive Performance Bounds for CIOQ Switches....Pages 577-588
Two-Stage Robust Network Design with Exponential Scenarios....Pages 589-600
An Optimal Incremental Algorithm for Minimizing Lateness with Rejection....Pages 601-610
More Robust Hashing: Cuckoo Hashing with a Stash....Pages 611-622
Better and Simpler Approximation Algorithms for the Stable Marriage Problem....Pages 623-634
Edit Distances and Factorisations of Even Permutations....Pages 635-646
Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count....Pages 647-659
Facility Location in Dynamic Geometric Data Streams....Pages 660-671
The Effects of Local Randomness in the Adversarial Queueing Model....Pages 672-683
Parallel Imaging Problem....Pages 684-695
An Online Algorithm for Finding the Longest Previous Factors....Pages 696-707
Collusion-Resistant Mechanisms with Verification Yielding Optimal Solutions....Pages 708-719
Improved BDD Algorithms for the Simulation of Quantum Circuits....Pages 720-731
Mobile Route Planning....Pages 732-743
How Reliable Are Practical Point-in-Polygon Strategies?....Pages 744-755
Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times – A Polymatroid Optimization Approach....Pages 756-767
Approximability of Average Completion Time Scheduling on Unrelated Machines....Pages 768-779
Relative Convex Hulls in Semi-dynamic Subdivisions....Pages 780-792
An Experimental Analysis of Robinson-Foulds Distance Matrix Algorithms....Pages 793-804
On the Size of the 3D Visibility Skeleton: Experimental Results....Pages 805-816
An Almost Space-Optimal Streaming Algorithm for Coresets in Fixed Dimensions....Pages 817-829
Deterministic Sampling Algorithms for Network Design....Pages 830-841
Back Matter....Pages -