{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:33:59Z","timestamp":1759847639530,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0830676CCF-0832797"],"award-info":[{"award-number":["CCF-0830676CCF-0832797"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1498698.1537602","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"source":"Crossref","is-referenced-by-count":9,"title":["Shortest-path feasibility algorithms"],"prefix":"10.1145","volume":"14","author":[{"given":"Boris V.","family":"Cherkassky","sequence":"first","affiliation":[{"name":"Central Economics and Mathematics Institute of the Russian Academy of Sciences"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loukas","family":"Georgiadis","sequence":"additional","affiliation":[{"name":"University of Western Macedonia, Kozani, Greece"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato F.","family":"Werneck","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"volume-title":"Proceedings of International Symposium on Circuits and Systems (ISCAS). IEEE","author":"Chandrachoodan N.","key":"e_1_2_1_2_1","unstructured":"Chandrachoodan , N. , Battacharyya , S. S. , and Liu , K. J. R. 2001. Adaptive negative-cycle detection in dynamic graphs . In Proceedings of International Symposium on Circuits and Systems (ISCAS). IEEE , Los Alamitos, CA, 163--166. Chandrachoodan, N., Battacharyya, S. S., and Liu, K. J. R. 2001. Adaptive negative-cycle detection in dynamic graphs. In Proceedings of International Symposium on Circuits and Systems (ISCAS). IEEE, Los Alamitos, CA, 163--166."},{"volume-title":"Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM","author":"Cherkassky B.","key":"e_1_2_1_3_1","unstructured":"Cherkassky , B. , Georgiadis , L. , Goldberg , A. V. , Tarjan , R. E. , and Werneck , R. F . 2008. Shortest-path feasibility algorithms: An experimental evaluation . In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM , Philadelphia, 118--132. Cherkassky, B., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., and Werneck, R. F. 2008. Shortest-path feasibility algorithms: An experimental evaluation. In Proceedings of the 10th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia, 118--132."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050058"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592101"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1027084.1027085"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90006-6"},{"key":"e_1_2_1_8_1","unstructured":"Demetrescu C. Goldberg A. and Johnson D. 2007. 9th DIMACS Implementation Challenge: Shortest-Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/.  Demetrescu C. Goldberg A. and Johnson D. 2007. 9th DIMACS Implementation Challenge: Shortest-Paths. http:\/\/www.dis.uniroma1.it\/~challenge9\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.1.161"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090304"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"volume-title":"Network Flow Theory. Tech. rep. P-932","author":"Ford Jr., L.","key":"e_1_2_1_12_1","unstructured":"Ford , Jr., L. 1956. Network Flow Theory. Tech. rep. P-932 , The Rand Corporation . Ford, Jr., L. 1956. Network Flow Theory. Tech. rep. P-932, The Rand Corporation."},{"key":"e_1_2_1_13_1","unstructured":"Ford Jr. L. and Fulkerson D. R. 1962. Flows in Networks. Princeton University Press Princeton NJ.  Ford Jr. L. and Fulkerson D. R. 1962. Flows in Networks. Princeton University Press Princeton NJ."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288320"},{"volume-title":"Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM","author":"Georgiadis L.","key":"e_1_2_1_16_1","unstructured":"Georgiadis , L. , Goldberg , A. V. , Tarjan , R. E. , and Werneck , R. F . 2009. An experimental study of minimum mean cycle algorithms . In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM , Philadelphia, 1--13. Georgiadis, L., Goldberg, A. V., Tarjan, R. E., and Werneck, R. F. 2009. An experimental study of minimum mean cycle algorithms. In Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX). SIAM, Philadelphia, 1--13."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792231179"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0893-9659(93)90022-F"},{"volume-title":"Proceedins IEEE\/ACM International Conference on CAD (ICCAD'03)","author":"Held S.","key":"e_1_2_1_19_1","unstructured":"Held , S. , Korte , B. , Massberg , J. , Ringe , M. , and Vygen , J . 2003. Clock scheduling and clocktree construction for high performance ASICs . In Proceedins IEEE\/ACM International Conference on CAD (ICCAD'03) . 232--239. Held, S., Korte, B., Massberg, J., Ringe, M., and Vygen, J. 2003. Clock scheduling and clocktree construction for high performance ASICs. In Proceedins IEEE\/ACM International Conference on CAD (ICCAD'03). 232--239."},{"key":"e_1_2_1_20_1","unstructured":"Kennington J. L. and Helgason R. V. 1980. Algorithms for Network Programming. John Wiley and Sons New York.   Kennington J. L. and Helgason R. V. 1980. Algorithms for Network Programming. John Wiley and Sons New York."},{"volume-title":"Proceedings of the 5th International Programming and Combinatorial Optimization Conference.","author":"Kolliopoulos S.","key":"e_1_2_1_21_1","unstructured":"Kolliopoulos , S. and Stein , C . 1996. Finding real-valued single-source shortest-paths in o(n<sup>3<\/sup>) expected time . In Proceedings of the 5th International Programming and Combinatorial Optimization Conference. Kolliopoulos, S. and Stein, C. 1996. Finding real-valued single-source shortest-paths in o(n<sup>3<\/sup>) expected time. In Proceedings of the 5th International Programming and Combinatorial Optimization Conference."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Symposium on the Theory of Switching","author":"Moore E. F.","year":"1959","unstructured":"Moore , E. F. 1959 . The Shortest-Path Through a Maze . In Proceedings of the International Symposium on the Theory of Switching . Harvard University Press, 285--292. Moore, E. F. 1959. The Shortest-Path Through a Maze. In Proceedings of the International Symposium on the Theory of Switching. Harvard University Press, 285--292."},{"key":"e_1_2_1_23_1","unstructured":"Nonato M. Pallottino S. and Xuewen B. 1999. SPT_L Shortest-Path Algorithms: Reviews New Proposals and Some Experimental Results. Tech. rep. TR-99-16 Dipartmento di Informatica Pisa University Italy.   Nonato M. Pallottino S. and Xuewen B. 1999. SPT_L Shortest-Path Algorithms: Reviews New Proposals and Some Experimental Results. Tech. rep. TR-99-16 Dipartmento di Informatica Pisa University Italy."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140206"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585517"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"volume-title":"rep","author":"Tarjan R. E.","key":"e_1_2_1_27_1","unstructured":"Tarjan , R. E. 1981. Shortest-Paths . Tech. rep ., AT&T Bell Laboratories , Murray Hill, NJ . Tarjan, R. E. 1981. Shortest-Paths. Tech. rep., AT&T Bell Laboratories, Murray Hill, NJ."},{"volume-title":"Data Structures and Network Algorithms","author":"Tarjan R. E.","key":"e_1_2_1_28_1","unstructured":"Tarjan , R. E. 1983. Data Structures and Network Algorithms . SIAM , Philadelphia . Tarjan, R. E. 1983. Data Structures and Network Algorithms. SIAM, Philadelphia."},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Tseitin G. 1970. On the Complexity of Derivation in Propositional Calculus. In Studies in Constructive Mathematics and Mathematical Logic. 115--125.  Tseitin G. 1970. On the Complexity of Derivation in Propositional Calculus. In Studies in Constructive Mathematics and Mathematical Logic. 115--125.","DOI":"10.1007\/978-1-4899-5327-8_25"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_58"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537602","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1498698.1537602","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:45:43Z","timestamp":1750250743000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1498698.1537602"}},"subtitle":["An experimental evaluation"],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":30,"alternative-id":["10.1145\/1498698.1537602"],"URL":"https:\/\/doi.org\/10.1145\/1498698.1537602","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2009,12]]}}}