Table of Contents

Invited Talk.- Some Open Questions Related to Cuckoo Hashing.- Trees.- Efficient Computation of the Characteristic Polynomial of a Tree and Related Tasks.- Improved Approximation Algorithms for Label Cover Problems.- A Linear Time Algorithm for L(2,1)-Labeling of Trees.- Geometry I.- On Inducing Polygons and Related Problems.- Computing 3D Periodic Triangulations.- Cauchy’s Theorem for Orthogonal Polyhedra of Genus 0.- Mathematical Programming.- Approximability of Sparse Integer Programs.- Iterative Rounding for Multi-Objective Optimization Problems.- A Global-Optimization Algorithm for Mixed-Integer Nonlinear Programs Having Separable Non-convexity.- Geometry II.- Constructing Delaunay Triangulations along Space-Filling Curves.- Piercing Translates and Homothets of a Convex Body.- Output-Sensitive Algorithms for Enumerating Minimal Transversals for Some Geometric Hypergraphs.- Algorithmic Game Theory I.- On Revenue Maximization in Second-Price Ad Auctions.- Clustering-Based Bidding Languages for Sponsored Search.- Altruism in Atomic Congestion Games.- Geometry III.- Geometric Spanners for Weighted Point Sets.- k-Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees.- Narrow-Shallow-Low-Light Trees with and without Steiner Points.- Algorithmic Game Theory II.- Bounded Budget Betweenness Centrality Game for Strategic Network Formations.- Exact and Approximate Equilibria for Optimal Group Network Formation.- On the Performance of Approximate Equilibria in Congestion Games.- Navigation and Routing.- Optimality and Competitiveness of Exploring Polygons by Mobile Robots.- Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.- Dynamic vs. Oblivious Routing in Network Design.- Invited Talk.- Algorithms Meet Art, Puzzles, andMagic.- Graphs and Point Sets.- Polynomial-Time Algorithm for the Leafage of Chordal Graphs.- Breaking the O(m 2 n) Barrier for Minimum Cycle Bases.- Shape Fitting on Point Sets with Probability Distributions.- Bioinformatics.- An Efficient Algorithm for Haplotype Inference on Pedigrees with a Small Number of Recombinants (Extended Abstract).- Complete Parsimony Haplotype Inference Problem and Algorithms.- Linear-Time Recognition of Probe Interval Graphs.- Wireless Communications.- Wireless Scheduling with Power Control.- On the Power of Uniform Power: Capacity of Wireless Networks with Bounded Resources.- Approximability of OFDMA Scheduling.- Flows, Matrices, Compression.- Maximum Flow in Directed Planar Graphs with Vertex Capacities.- A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication.- On Optimally Partitioning a Text to Improve Its Compression.- Scheduling.- An Average-Case Analysis for Rate-Monotonic Multiprocessor Real-Time Scheduling.- Minimizing Maximum Response Time and Delay Factor in Broadcast Scheduling.- Preemptive Online Scheduling with Reordering.- Streaming.- d-Dimensional Knapsack in the Streaming Model.- Sparse Cut Projections in Graph Streams.- Bipartite Graph Matchings in the Semi-streaming Model.- Online Algorithms.- The Oil Searching Problem.- Hyperbolic Dovetailing.- Bluetooth and Dial a Ride.- On the Expansion and Diameter of Bluetooth-Like Topologies.- Minimum Makespan Multi-vehicle Dial-a-Ride.- Invited Talk.- Google’s Auction for TV Ads.- Decomposition and Covering.- Inclusion/Exclusion Meets Measure and Conquer.- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution.- Counting Paths and Packings in Halves.- Algorithm Engineering.- Accelerating Multi-modal Route Planning by Access-Nodes.-Parallel Algorithms for Mean-Payoff Games: An Experimental Evaluation.- Experimental Study of FPT Algorithms for the Directed Feedback Vertex Set Problem.- Parameterized Algorithms I.- Fast Evaluation of Interlace Polynomials on Graphs of Bounded Treewidth.- Kernel Bounds for Disjoint Cycles and Disjoint Paths.- Constant Ratio Fixed-Parameter Approximation of the Edge Multicut Problem.- Data Structures.- Rank-Pairing Heaps.- 3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit.- Hash, Displace, and Compress.- Parameterized Algorithms II.- Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels.- Contraction Bidimensionality: The Accurate Picture.- Minimizing Movement: Fixed-Parameter Tractability.- Hashing and Lowest Common Ancestor.- Storing a Compressed Function with Constant Time Access.- Experimental Variations of a Theoretically Good Retrieval Data Structure.- Short Labels for Lowest Common Ancestors in Trees.- Best Paper Awards.- Disproof of the Neighborhood Conjecture with Implications to SAT.- Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard.