WEA 2007 - 6th Workshop on Experimental Algorithms
June 6-8, 2007
Rome Italy

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

Important Dates


Jan 27, 2007


Mar 7, 2007

Camera Ready

Mar 21, 2007

Early Registration

April 20, 2007

Welcome cocktail

June 5, 2007


June 6-8, 2007

Call for Papers

PDF iconPDF format

ps iconPostScript

TXT iconPlain text

Click to see photos of Rome
Maintained by Saverio Caminiti