TY - GEN
T1 - Shortest path feasibility algorithms
T2 - 10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08
AU - Cherkassky, Boris V.
AU - Georgiadis, Loukas
AU - Goldberg, Andrew V.
AU - Tarjan, Robert E.
AU - Werneck, Renato F.
PY - 2008/1/1
Y1 - 2008/1/1
N2 - This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area.
AB - This is an experimental study of algorithms for the shortest path feasibility problem: Given a directed weighted graph, find a negative cycle or present a short proof that none exists. We study previously known and new algorithms. Our testbed is more extensive than those previously used, including both static and incremental problems, as well as worst-case instances. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area.
UR - http://www.scopus.com/inward/record.url?scp=58349105981&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=58349105981&partnerID=8YFLogxK
U2 - 10.1137/1.9781611972887.12
DO - 10.1137/1.9781611972887.12
M3 - Conference contribution
AN - SCOPUS:58349105981
SN - 9780898716535
T3 - Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics
SP - 118
EP - 132
BT - Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics
PB - Curran Associates Inc.
Y2 - 19 January 2008 through 19 January 2008
ER -