The Ninth DIMACS Implementation Challenge:
The Shortest Path Problem

November 13 - 14, 2006
DIMACS Center, Rutgers University, Piscataway, NJ

Organizers:

Camil Demetrescu, University of Rome "La Sapienza"

Andrew Goldberg, Microsoft Research

David Johnson, AT&T Labs - Research, dsj@research.att.com

Special thanks go to Microsoft Research for its contribution to this meeting.

Workshop Program:

Monday, November 13, 2006
 
 8:15 -  9:00  Breakfast and Registration

 9:00 -  9:30  Opening Remarks
               Fred Roberts, DIMACS Director; 

               Competition Problem Defined
               Challenge Organizers

 9:30 - 10:00  Coffee Break, competition starts

10:00 - 10:40  An Experimental Evaluation of Point-To-Point Shortest Path
               Calculation on Roadnetworks with Precalculated Edge-Flags
               Ulrich Lauther, Siemens AG, Germany

10:40 - 11:20  Fast Point-to-Point Shortest Path Computations with Arc-Flags
               Heiko Schilling, TU Berlin, Germany

11:20 - 12:00  High-Performance Multi-Level Graphs
               Kirill Müller, Universität Karlsruhe, Germany

12:00 -  1:30  Lunch

 1:30 -  2:10  Better Landmarks within Reach
               Renato F. Werneck, Microsoft Research  -  Silicon Valley, USA

 2:10 -  2:50  Highway Hierarchies Star
               Daniel Delling and Dominik Schultes, Universität Karlsruhe, Germany

 2:50 -  3:20  Coffee Break

 3:20 -  4:00  Implementations and Empirical Comparison of 
               K Shortest Loopless Path Algorithms
               Marta Pascoal, University of Coimbra and INESC - Coimbra, Portugal

 4:40 -  5:20  K Shortest Path Algorithms
               Jose' L. Santos, University of Coimbra, Portugal

 5:30 -  6:45  Reception

 6:45 -  7:30  Panel discussion

Tuesday, November 14, 2006

 8:15 -  9:00  Breakfast and Registration

 9:00 -  9:40  TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing
               Rouven Naujoks, Max-Planck-Institute for Informatics

 9:40 - 10:20  Robust, Almost Constant Time Shortest-Path Queries on Road Networks
               Dominik Schultes, Universität Karlsruhe, Germany

10:20 - 10:50  Coffee Break

10:50 - 11:30  Implementations of Routing Algorithms for Transportation Networks
               Martin Holzer, and Goran Konjevod 
            
11:30 - 12:20  INVITED TALK
               Solving Massive Graph Problems using Petascale Computing
               David A. Bader, Georgia Institute of Technology

12:20 -  1:50  Lunch
               Competition results due

 1:50 -  2:30  Breadth First Search on Massive Graphs
               Vitaly Osipov, Max Planck Institute for Informatics, Germany

 2:20 -  2:50  Competition results announced/discussed

 2:50 -  3:20  Coffee Break

 3:20 -  4:00  Parallel Shortest Path Algorithms for Solving Large-Scale Instances
               Kamesh Madduri, Georgia Institute of Technology

 4:00 -  4:40  Single-Source Shortest Paths with the 
               Parallel Boost Graph Library
               Nick Edmonds, Indiana University, USA

 4:40 -  5:10  Conclusion

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage