The Collection of
Computer Science Bibliographies

Bibliography on algorithms for k shortest paths

[   About   |  Browse   |   Statistics   ]

Number of references:499Last update:March 23, 2001
Number of online publications:100Supported:Unknown
Most recent reference:February 2001

Information on the Bibliography

Author:
David Eppstein <eppstein @ ics . uci . edu> (email mangled to prevent spamming)
Dept. of Information and Computer Science
University of California
Irvine, CA 92717-3425
USA
Abstract:
This bibliography lists papers studying a generalization of the shortest path problem: not just finding the single shortest path between a pair of nodes, but instead listing a sequence of the k shortest paths. Methods for finding k shortest paths have been applied to many applications, for two reasons.
  1. One may wish to find a path that satisfies certain constraints beyond having a small length, but those other constraints may be ill-defined or hard to optimize. A typical solution is to compute several short paths and then choose among them by considering the other criteria.
  2. By computing more than one shortest path, one can determine how sensitive the optimal solution is to variation of the problem's parameters. The bibliography also includes related work on listing k best solutions to other combinatorial problems.
Keywords:
shortest paths, k shortest paths, k most vital arcs, dynamic programming, sequence alignment, knapsack problem, k minimum spanning trees

Browsing the bibliography

Bibliographic Statistics

Types:
article(302), inproceedings(140), techreport(22), phdthesis(17), incollection(7), mastersthesis(6), book(4), misc(1)
Fields:
title(499), year(497), author(457), pages(347), volume(346), journal(309), number(266), abstract(246), publisher(224), month(175), booktitle(145), review(73), reviews(73), text(59), url(35), series(29), note(24), school(23), institution(20), editor(12), annote(9), address(7), comment(4), type(4), organization(2), howpublished(1), site(1), summary(1)
Distribution of publication dates:
Distribution of publication dates

Valid XHTML 1.1!  Valid CSS!