Thumbnail
Access Restriction
Subscribed

Author Cherkassky, Boris V. ♦ Georgiadis, Loukas ♦ Goldberg, Andrew V. ♦ Tarjan, Robert E. ♦ Werneck, Renato F.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Shortest paths ♦ Feasibility ♦ Negative cycles
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 new algorithms) has very robust performance in practice. Our work advances the state of the art in the area.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-01-05
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 14
Page Count 31
Starting Page 2.7
Ending Page 2.37


Open content in new tab

   Open content in new tab
Source: ACM Digital Library