WEA 2007

6th Workshop on Experimental Algorithms

June 6-8, 2007 — Rome Italy

Final Program

Computing equipment: There will be a wireless network for WEA participants, LCD/overhead projectors, and a laptop with Windows XP equipped with PowerPoint/Acrobat Reader.

Tuesday June 5, 2007

15:30-19:30 Registration desk and Welcome cocktail

Wednesday June 6, 2007

8.50-9.00 Opening remarks

9.00-10.00 "Engineering Fast Route Planning Algorithms", Peter Sanders, Universität Karlsruhe. (Invited talk)

Session 1: Route planning (chair: Jan Vahrenhold)

10.00-10.25 "Better Landmarks within Reach", Andrew Goldberg, Haim Kaplan, and Renato Werneck.

10.25-10.50 "Landmark-Based Routing in Dynamic Graphs", Daniel Delling and Dorothea Wagner.

10.50-11.15 "Dynamic Multi-Level Highway Node Routing", Dominik Schultes and Peter Sanders.

11.15-11.40 Coffee Break

Session 2: Dynamic trees, skip lists, and bloom filters (chair: Giuseppe F. Italiano)

11.40-12.05 "Dynamic Trees in Practice", Robert Tarjan and Renato Werneck.

12.05-12.30 "On the Cost of Persistence and Authentication in Skip Lists", Michael Goodrich, Charalampos Papamanthou, and Roberto Tamassia.

12.30-12.55 "Cache-, Hash- and Space-Efficient Bloom Filters", Felix Putze, Peter Sanders, and Johannes Singler.

13.00-14.20 Lunch break

Session 3: Crossing minimization, TSP, and vehicle routing (chair:Giorgio Ausiello)

14.20-14.45 "Crossing Minimization in Weighted Bipartite Graphs", Olca Arda Çakıroğlu, Cesim Erten, Ömer Karataş, and Melih Sözdinler.

14.45-15.10 "Fast minimum-weight double-tree shortcutting for Metric TSP", Vladimir Deineko and Alexander Tiskin.

15.10-15.35 "A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem", Artur Alves Pessoa, Marcus Poggi, and Eduardo Uchoa.

15.35-16.00 Coffee Break

Session 4: Network routing and stability (chair: TBA)

16.00-16.25 "Simple and Efficient Geographic Routing around Obstacles for Wireless Sensor Networks", Olivier Powell and Sotiris Nikoletseas.

16.25-16.50 "A distributed primal-dual heuristic for Steiner Problems in Networks", Marcelo Santos, Lucia Drummond, and Eduardo Uchoa.

16.50-17.15 "An Experimental Study of Stability in Heterogenous Networks", Maria Chroni, Dimitrios Koukopoulos, and Stavros Nikolopoulos.

Thursday June 7, 2007

9.00-10.00 "An Alternative Ranking Problem for Search Engines", Corinna Cortes, Google Research. (Invited talk)

Session 5: Strings and range searching (chair: Robert Sedgewick)

10.00-10.25 "Simple compression code supporting random access and fast string matching", Kimmo Fredriksson and Fedor Nikitin.

10.25-10.50 "Engineering a Compressed Suffix Tree Implementation", Niko Välimäki, Wolfgang Gerlach, Kashyap Dixit, and Veli Mäkinen.

10.50-11.15 "Simple space-time trade-offs for AESA", Karina Figueroa and Kimmo Fredriksson.

11.15-11.40 Coffee Break

Session 6: Matching, Flows, and Spanners (chair: Jan Vahrenhold)

11.40-12.05 "Engineering Algorithms for Approximate Weighted Matching", Jens Maue and Peter Sanders.

12.05-12.30 "Experimental Evaluation of Parametric Max-Flow Algorithms", Maxim Babenko, Jonathan Derryberry, Andrew Goldberg, Robert Tarjan, and Yunhong Zhou.

12.30-12.55 "Experimental study of geometric t-spanners: a running time comparison", Mohammad Farshi and Joachim Gudmundsson.

13.00-14.20 Lunch break

15.30 Social Event

Friday June 8, 2007

9.00-10.00 "Random models for geometric graphs", Maria Serna, Universitat Politècnica de Catalunya. (Invited talk)

Session 7: Covering, Coloring, and Partitioning (chair: Rudolf Fleischer)

10.00-10.25 "Vertex Cover Approximations on Random Graphs", Eyjolfur Asgeirsson and Cliff Stein.

10.25-10.50 "Optimal Edge Deletions for Signed Graph Balancing", Falk Hüffner, Nadja Betzler, and Rolf Niedermeier.

10.50-11.15 "Algorithms for the Balanced Edge Partitioning Problem", Ekaterina Smorodkina, Mayur Thakur, and Daniel Tauritz.

11.15-11.40 Coffee Break

Session 8: Applications (chair: Renato Werneck)

11.40-12.05 "Experimental Evaluation of Algorithms for IP Table Minimization", Angelo Fanelli, Michele Flammini, Domenico Mango, Giovanna Melideo, and Luca Moscardelli.

12.05-12.30 "Algorithms for longer OLED Lifetime", Friedrich Eisenbrand, Andreas Karrenbauer, and Chihao Xu.

12.30-12.55 "Improving Tree Search in Phylogenetic Reconstruction from Genome Rearrangement Data", Fei Ye, Yan Guo, Andrew Lawson, and Jijun Tang.

13.00-14.20 Lunch break

Session 9: Spanning trees (chair: Camil Demetrescu)

14.20-14.45 "Benchmarks for Strictly Fundamental Cycle Bases", Christian Liebchen, Gregor Wünsch, Ekkehard Köhler, Alexander Reich, and Romeo Rizzi.

14.45-15.10 "A Primal Branch-and-Cut Algorithm for the Degree-Constrained Minimum Spanning Tree Problem", Markus Behle, Michael Jünger, and Frauke Liers.

15.10-15.35 "Experimental Analysis of Algorithms for Updating Minimum Spanning Trees on Graphs Subject to Changes on Edge Weights", Celso Ribeiro and Rodrigo Toso.

15.35-16.00 Coffee Break

Session 10: Packing and auctions (chair: TBA)

16.00-16.25 "An efficient implementation for the 0-1 multi-objective knapsack problem", Cristina Bazgan, Hadrien Hugot, and Daniel Vanderpooten.

16.25-16.50 "Trunk packing revisited", Ernst Althaus, Tobias Baumann, Elmar Schoemer, and Kai Werth.

16.50-17.15 "Exact algorithms for the matrix bid auction", Dries Goossens and Frits Spieksma.

17.15 Adjourn