Algorithms - ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings

Front Matter....Pages -
Some Open Questions Related to Cuckoo Hashing....Pages 1-10
Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks....Pages 11-22
Improved Approximation Algorithms for Label Cover Problems....Pages 23-34
A Linear Time Algorithm for L (2,1)-Labeling of Trees....Pages 35-46
On Inducing Polygons and Related Problems....Pages 47-58
Computing 3D Periodic Triangulations....Pages 59-70
Cauchy’s Theorem for Orthogonal Polyhedra of Genus 0....Pages 71-82
Approximability of Sparse Integer Programs....Pages 83-94
Iterative Rounding for Multi-Objective Optimization Problems....Pages 95-106
A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity....Pages 107-118
Constructing Delaunay Triangulations along Space-Filling Curves....Pages 119-130
Piercing Translates and Homothets of a Convex Body....Pages 131-142
Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs....Pages 143-154
On Revenue Maximization in Second-Price Ad Auctions....Pages 155-166
Clustering-Based Bidding Languages for Sponsored Search....Pages 167-178
Altruism in Atomic Congestion Games....Pages 179-189
Geometric Spanners for Weighted Point Sets....Pages 190-202
 k -Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees....Pages 203-214
Narrow-Shallow-Low-Light Trees with and without Steiner Points....Pages 215-226
Bounded Budget Betweenness Centrality Game for Strategic Network Formations....Pages 227-238
Exact and Approximate Equilibria for Optimal Group Network Formation....Pages 239-250
On the Performance of Approximate Equilibria in Congestion Games....Pages 251-262
Optimality and Competitiveness of Exploring Polygons by Mobile Robots....Pages 263-274
Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links....Pages 275-276
Dynamic vs. Oblivious Routing in Network Design....Pages 277-288
Algorithms Meet Art, Puzzles, and Magic....Pages 289-289
Polynomial-Time Algorithm for the Leafage of Chordal Graphs....Pages 290-300
Breaking the O ( m 2 n ) Barrier for Minimum Cycle Bases....Pages 301-312
Shape Fitting on Point Sets with Probability Distributions....Pages 313-324
An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract)....Pages 325-336
Complete Parsimony Haplotype Inference Problem and Algorithms....Pages 337-348
Linear-Time Recognition of Probe Interval Graphs....Pages 349-360
Wireless Scheduling with Power Control....Pages 361-372
On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources....Pages 373-384
Approximability of OFDMA Scheduling....Pages 385-396
Maximum Flow in Directed Planar Graphs with Vertex Capacities....Pages 397-407
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication....Pages 408-419
On Optimally Partitioning a Text to Improve Its Compression....Pages 420-431
An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling....Pages 432-443
Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling....Pages 444-455
Preemptive Online Scheduling with Reordering....Pages 456-467
 d -Dimensional Knapsack in the Streaming Model....Pages 468-479
Sparse Cut Projections in Graph Streams....Pages 480-491
Bipartite Graph Matchings in the Semi-streaming Model....Pages 492-503
The Oil Searching Problem....Pages 504-515
Hyperbolic Dovetailing....Pages 516-527
On the Expansion and Diameter of Bluetooth-Like Topologies....Pages 528-539
Minimum Makespan Multi-vehicle Dial-a-Ride....Pages 540-552
Google’s Auction for TV Ads....Pages 553-553
Inclusion/Exclusion Meets Measure and Conquer....Pages 554-565
Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution....Pages 566-577
Counting Paths and Packings in Halves....Pages 578-586
Accelerating Multi-modal Route Planning by Access-Nodes....Pages 587-598
Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation....Pages 599-610
Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem....Pages 611-622
Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth....Pages 623-634
Kernel Bounds for Disjoint Cycles and Disjoint Paths....Pages 635-646
Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem....Pages 647-658
Rank-Pairing Heaps....Pages 659-670
3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit....Pages 671-681
Hash, Displace, and Compress....Pages 682-693
Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels....Pages 694-705
Contraction Bidimensionality: The Accurate Picture....Pages 706-717
Minimizing Movement: Fixed-Parameter Tractability....Pages 718-729
Storing a Compressed Function with Constant Time Access....Pages 730-741
Experimental Variations of a Theoretically Good Retrieval Data Structure....Pages 742-751
Short Labels for Lowest Common Ancestors in Trees....Pages 752-763
Disproof of the Neighborhood Conjecture with Implications to SAT....Pages 764-775
Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard....Pages 776-787
Back Matter....Pages -