List of accepted papers for ESA 2007:


Design and Analysis:

Petr Hlineny and Sang-il Oum. 
Finding branch-decompositions and rank-decompositions 

Mario Szegedy and Mikkel Thorup.
 On the variance of subset sum estimation 

Noga Alon and Raphael Yuster.
Fast algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in graphs with a (not so) small vertex cover 

Yuval Lando and Zeev Nutov. 
On minimum power connectivity problems 

Mikkel Thorup. 
Compact Oracles for Approximate Distances around Obstacles in the Plane 

Wolfgang Bein, Lawrence Larmore and John Noga. 
Equitable Revisited 

Reuven Bar-Yehuda, Guy Flysher, Julian Mestre and Dror Rawitz. 
Approximation of Partial Capacitated Vertex Cover 

Israel Beniaminy, Zeev Nutov and Meir Ovadia. 
Approximating Interval Scheduling Problems with Bounded Profits 

Justo Puerto, Antonio M. Rodriguez-Chia and Arie Tamir. 
New results on Minimax Regret Single Facility Location Problems on Networks 

Amihood Amir, Tzvika Hartman, Oren Kapah, Avivit Levy and Ely Porat. 
On The Cost of Interchange Rearrangement in Strings 

Alexander Souza and Martin Hoefer. 
Tradeoffs and Average-Case Equilibria in Selfish Routing 

Frank Kammer. 
Determining the smallest k such that G is k-outerplanar 

Rina Panigrahy and Dilys Thomas. 
Finding Frequent Elements in non-bursty Streams 

Amos Israeli, Dror Rawitz and Oran Sharon. 
On the Complexity of Sequential Rectangle Placement in IEEE 802.16/WiMAX Systems 

Aristides Gionis and Tamir Tassa. 
k-Anonymization with Minimal Loss of Information 

Jakub Pawlewicz. 
Order Statistics in the Farey Sequences in Sublinear Time 

Amotz Bar-Noy and Joanna Klukowska. 
Finding Mobile Data: Efficiency vs. Location Inaccuracy 

Alexa Sharp. 
Distance Coloring 

Petra Berenbrink and Oliver Schulte. 
Evolutionary Equilibrium in Bayesian Routing Games: Specialization and Niche Formation 

Dimitris Fotakis. 
Stackelberg Strategies for Atomic Congestion Games 

Petra Berenbrink, Tom Friedetzky, Iman Hajiresouliha and Zengjian Hu. 
Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks 

Jihuan Ding, Tomas Ebenlendr, Jiri Sgall and Guochuan Zhang. 
Online scheduling of equal-length jobs on parallel machines 

Chien-Chung Huang. 
Two's Company, Three's a Crowd: Stable Family and Threesome Roommates Problems 

Shankar Kalyanaraman and Christopher Umans. 
Algorithms for Playing Games with Limited Randomness 

Niv Buchbinder, Kamal Jain and Joseph (Seffi) Naor. 
Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue 

Nikhil Bansal, Niv Buchbinder, Anupam Gupta and Seffi Naor. 
An O(log k)-competitive Algorithm for Metric Bipartite Matching 

Otfried Cheong, Hazel Everett, Marc Glisse, Joachim Gudmundsson, Samuel Hornus, Sylvain Lazard, Mira Lee and Hyeon-Suk Na. 
Farthest-polygon Voronoi diagrams 

Sriram Pemmaraju and Imran Pirwani. 
Good Quality Virtual Realization of Unit Ball Graphs 

Julian Lorenz, Konstantinos Panagiotou and Angelika Steger. 
Optimal Algorithms for k-Search with Application in Option Pricing 

Alexander Grigoriev, Joyce van Loon, Maxim Sviridenko, Marc Uetz and Tjark Vredeveld. 
Bundle Pricing with Comparable Items 

Christoph Durr and Thang Nguyen Kim. 
Nash equilibria in Voronoi games on graphs 

Philippe Baptiste, Marek Chrobak and Christoph Durr. 
Polynomial Time Algorithms for Minimum Energy Scheduling 

Chi-Yuan Chan, Hung-I Yu, Wing-Kai Hon and Biing-Feng Wang. 
A Faster Query Algorithm for the Text Fingerprinting Problem 

Maren Martens, Fernanda Salazar and Martin Skutella. 
Convex Combinations of Single Source Unsplittable Flows 

Haim Kaplan, Natan Rubin and Micha Sharir. 
Linear Data Structures for Fast Ray-Shooting amidst Convex Polyhedra 

Anupam Gupta, MohammadTaghi Hajiaghayi, Viswanath Nagarajan and R Ravi. 
Dial a Ride from k-forest 

Alessandro Panconesi, Fabrizio Grandoni and Emilio De Santis. 
Fast Low Degree Connectivity of Ad-Hoc Networks via Percolation 

Miroslaw Kowaluk and Andrzej Lingas. 
Unique Lowest Common Ancestors in Dags are Almost as Easy as Matrix Multiplication 

Khaled Elbassioni, Rene Sitters and Yan Zhang. 
A Quasi-PTAS for Profit-Maximizing Pricing on Line Graphs 

Vineet Goyal, Anupam Gupta, Stefano Leonardi and R Ravi. 
Pricing Tree Access Networks with Connected Backbones 

Martin Mares and Milan Straka. 
Linear-Time Ranking of Permutations 

Alexander Golynski, Roberto Grossi, Ankur Gupta, Rajeev Raman and Srinivasa Rao Satti. 
On the Size of Succinct Indices 

Samir Khuller, Azarakhsh Malekian and Julian Mestre. 
To Fill or not to Fill: The Gas Station Problem 

Gianni Franceschini, S Muthukrishnan and Mihai Patrascu. 
Radix Sorting With No Extra Space 

Krzysztof Diks and Piotr Sankowski. 
Dynamic Plane Transitive Closure 

Michal Forisek, Branislav Katreniak, Jana Katreniakova, Rastislav Kralovic, Richard Kralovic, Vladimir Koutny, Dana Pardubska, Tomas Plachetka and Branislav Rovan.
Online Bandwidth Allocation 

Koji Kobayashi and Kazuya Okamoto. 
Improved Upper Bounds on the Competitive Ratio for Online Realtime Scheduling 


Engineering and Applications Track:

Cristina Bazgan, Hadrien Hugot and Daniel Vanderpooten. 
A practical efficient fptas for the 0-1 multi-objective knapsack problem 

Susanne Albers and Tobias Jacobs. 
An Experimental Study of New and Known Online Packet Buffering Algorithms 

Giorgio Ausiello, Camil Demetrescu, Paolo G. Franciosa, Giuseppe Italiano and Andrea Ribichini. 
Small Stretch Spanners in the Streaming Model: New Algorithms and Experiments 

Felix K?nig, Marco L?bbecke, Rolf M?hring, Guido Schaefer and Ines Spenke. 
Solutions to Real-World Instances of PSPACE-Complete Stacking 

Laurent Dupont, Michael Hemmer, Sylvain Petitjean and Elmar Sch?mer. 
Complete, Exact and Efficient Implementation for Computing the Adjacency Graph of an Arrangment of Quadrics 

Markus Chimani, Maria Kandyba and Petra Mutzel. 
A New ILP Formulation for 2-Root-Connected Prize-Collecting Steiner Networks 

Luciana Buriol, Gereon Frahling, Stefano Leonardi and Christian Sohler. 
Estimating Clustering Indexes in Data Streams 

Julien Robert and Nicolas Schabanel. 
Non-Clairvoyant Batch Set Scheduling: Fairness is Fair enough 

Laurent Muller and Martin Zachariasen. 
Fast and Compact Oracles for Approximate Shortest Paths in Planar Graphs 

Arie Koster, Adrian Zymolka and Manuel Kutschka. 
Algorithms to separate {0,1/2}-Chvatal-Gomory cuts 

Stefan Eckhardt, Andreas Michael M?hling and Johannes Nowak. 
Fast Lowest Common Ancestor Computations in Dags 

Eric Berberich, Efi Fogel, Dan Halperin, Kurt Mehlhorn and Ron Wein. 
Sweeping and Maintaining Two-Dimensional Arrangements on Surfaces: A First Step 

Peter Hachenberger. 
Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyedra in Convex Pieces