Shortest path feasibility algorithms: An experimental evaluation

Boris V. Cherkassky, Loukas Georgiadis, Andrew V. Goldberg, Robert E. Tarjan, Renato F. Werneck

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics
PublisherCurran Associates Inc.
Pages118-132
Number of pages15
ISBN (Print)9780898716535
DOIs
StatePublished - Jan 1 2008
Event10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08 - San Francisco, CA, United States
Duration: Jan 19 2008Jan 19 2008

Publication series

NameProceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics

Other

Other10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08
CountryUnited States
CitySan Francisco, CA
Period1/19/081/19/08

All Science Journal Classification (ASJC) codes

  • Engineering(all)
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Shortest path feasibility algorithms: An experimental evaluation'. Together they form a unique fingerprint.

  • Cite this

    Cherkassky, B. V., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. (2008). Shortest path feasibility algorithms: An experimental evaluation. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics (pp. 118-132). (Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics). Curran Associates Inc.. https://doi.org/10.1137/1.9781611972887.12