Shortest path feasibility algorithms: An experimental evaluation

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

doi:10.1137/1.9781611972887.12

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 proceeding › Conference contribution

8 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 language	English (US)
Title of host publication	Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics
Publisher	Curran Associates Inc.
Pages	118-132
Number of pages	15
ISBN (Print)	9780898716535
DOIs	https://doi.org/10.1137/1.9781611972887.12
State	Published - Jan 1 2008
Event	10th 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 2008 → Jan 19 2008

Publication series

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

Other

Other	10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08
Country/Territory	United States
City	San Francisco, CA
Period	1/19/08 → 1/19/08

All Science Journal Classification (ASJC) codes

Engineering(all)
Applied Mathematics

Access to Document

10.1137/1.9781611972887.12

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

Cherkassky, Boris V. ; Georgiadis, Loukas ; Goldberg, Andrew V. et al. / Shortest path feasibility algorithms : An experimental evaluation. Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics. Curran Associates Inc., 2008. pp. 118-132 (Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics).

@inproceedings{3f21d5babfc4454db5545fe56ca375c7,

title = "Shortest path feasibility algorithms: An experimental evaluation",

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.",

author = "Cherkassky, {Boris V.} and Loukas Georgiadis and Goldberg, {Andrew V.} and Tarjan, {Robert E.} and Werneck, {Renato F.}",

year = "2008",

month = jan,

day = "1",

doi = "10.1137/1.9781611972887.12",

language = "English (US)",

isbn = "9780898716535",

series = "Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics",

publisher = "Curran Associates Inc.",

pages = "118--132",

booktitle = "Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics",

note = "10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08 ; Conference date: 19-01-2008 Through 19-01-2008",

}

Cherkassky, BV, Georgiadis, L, Goldberg, AV, Tarjan, RE & Werneck, RF 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. Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics, Curran Associates Inc., pp. 118-132, 10th Workshop on Algorithm Engineering and Experiments, ALENEX'08 and 5th Workshop on Analytic Algorithmics and Combinatorics, ANALCO'08, San Francisco, CA, United States, 1/19/08. https://doi.org/10.1137/1.9781611972887.12

Shortest path feasibility algorithms : An experimental evaluation. / Cherkassky, Boris V.; Georgiadis, Loukas; Goldberg, Andrew V. et al.

Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics. Curran Associates Inc., 2008. p. 118-132 (Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Cherkassky BV, Georgiadis L, Goldberg AV, Tarjan RE, Werneck RF. 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. Curran Associates Inc. 2008. p. 118-132. (Proceedings of the 10th Workshop on Algorithm Engineering and Experiments and the 5th Workshop on Analytic Algorithmics and Combinatorics). doi: 10.1137/1.9781611972887.12

Shortest path feasibility algorithms: An experimental evaluation

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this