DIMACS - Series in Discrete Mathematics and Theoretical Computer Science
Volume: 74; 2009; 319 pp; Hardcover
MSC: Primary 05; 68; 90;
Print ISBN: 978-0-8218-4383-3
Product Code: DIMACS/74
List Price: $110.00
Individual Member Price: $88.00
The Shortest Path Problem: Ninth DIMACS Implementation ChallengeShare this page
Edited by Camil Demetrescu; Andrew V. Goldberg; David S. Johnson
A co-publication of the AMS and DIMACS
Shortest path problems are among the most fundamental combinatorial
optimization problems with many applications, both direct and as
subroutines. They arise naturally in a remarkable number of real-world
settings. A limited list includes transportation planning, network
optimization, packet routing, image segmentation, speech recognition,
document formatting, robotics, compilers, traffic information systems, and
dataflow analysis. Shortest path algorithms have been studied since the
1950's and still remain an active area of research.
This volume reports on the research carried out by participants during the Ninth DIMACS Implementation Challenge, which led to several improvements of the state of the art in shortest path algorithms. The infrastructure developed during the Challenge facilitated further research in the area, leading to substantial follow-up work as well as to better and more uniform experimental standards. The results of the Challenge included new cutting-edge techniques for emerging applications such as GPS navigation systems, providing experimental evidence of the most effective algorithms in several real-world settings.
Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).
Table of Contents
Table of Contents
The Shortest Path Problem: Ninth DIMACS Implementation Challenge
Graduate students and research mathematicians interested in algorithms and combinatorial optimization problems.