{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T10:14:07Z","timestamp":1773656047386,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540616801","type":"print"},{"value":"9783540706670","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61680-2_67","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:11:14Z","timestamp":1330276274000},"page":"349-363","source":"Crossref","is-referenced-by-count":23,"title":["Negative-cycle detection algorithms"],"prefix":"10.1007","author":[{"given":"Boris V.","family":"Cherkassky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,6]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. E. Bellman","year":"1958","unstructured":"R. E. Bellman. On a Routing Problem. Quart. Appl. Math., 16:87\u201390, 1958.","journal-title":"Quart. Appl. Math."},{"key":"26_CR2","unstructured":"B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest Paths Algorithms: Theory and Experimental Evaluation. In Proc. 5th ACM-SIAM Symposium on Discrete Algorithms, pages 516\u2013525, 1994. To appear in Math. Prog."},{"key":"26_CR3","volume-title":"Introduction to Algorithms","author":"T. H. Cormen","year":"1990","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. MIT Press, Cambridge, MA, 1990."},{"key":"26_CR4","first-page":"359","volume-title":"Activity Analysis and Production and Allocation","author":"G. B. Dantzig","year":"1951","unstructured":"G. B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T. C. Koopmans, editor, Activity Analysis and Production and Allocation, pages 359\u2013373. Wiley, New York, 1951."},{"key":"26_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1287\/opre.27.1.161","volume":"27","author":"E. V. Denardo","year":"1979","unstructured":"E. V. Denardo and B. L. Fox. Shortest-Route Methods: 1. Reaching, Pruning, and Buckets. Oper. Res., 27:161\u2013186, 1979.","journal-title":"Oper. Res."},{"key":"26_CR6","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/net.3230090304","volume":"9","author":"R. B. Dial","year":"1979","unstructured":"R. B. Dial, F. Glover, D. Karney, and D. Klingman. A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees. Networks, 9:215\u2013248, 1979.","journal-title":"Networks"},{"key":"26_CR7","unstructured":"L. Ford. Network Flow Theory. Technical Report P-932, The Rand Corporation, 1956."},{"key":"26_CR8","volume-title":"Flows in Networks","author":"L. R. Ford Jr.","year":"1962","unstructured":"L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton Univ. Press, Princeton, NJ, 1962."},{"key":"26_CR9","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF02288320","volume":"13","author":"G. Gallo","year":"1988","unstructured":"G. Gallo and S. Pallottino. Shortest Paths Algorithms. Annals of Oper. Res., 13:3\u201379, 1988.","journal-title":"Annals of Oper. Res."},{"key":"26_CR10","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1002\/net.3230140103","volume":"14","author":"F. Glover","year":"1984","unstructured":"F. Glover, R. Glover, and D. Klingman. Computational Study of an Improved Shortest Path Algorithm. Networks, 14:25\u201337, 1984.","journal-title":"Networks"},{"key":"26_CR11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1287\/opre.33.1.65","volume":"33","author":"F. Glover","year":"1985","unstructured":"F. Glover, D. Klingman, and N. Phillips. A New Polynomially Bounded Shortest Paths Algorithm. Oper. Res., 33:65\u201373, 1985.","journal-title":"Oper. Res."},{"key":"26_CR12","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"A. V. Goldberg","year":"1995","unstructured":"A. V. Goldberg. Scaling Algorithms for the Shortest Paths Problem. SIAM J. Comput., 24:494\u2013504, 1995.","journal-title":"SIAM J. Comput."},{"key":"26_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0893-9659(93)90022-F","volume":"6","author":"A. V. Goldberg","year":"1993","unstructured":"A. V. Goldberg and T. Radzik. A Heuristic Improvement of the Bellman-Ford Algorithm. Applied Math. Let., 6:3\u20136, 1993.","journal-title":"Applied Math. Let."},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0305-0548(88)90052-4","volume":"15","author":"M. S. Hung","year":"1988","unstructured":"M. S. Hung and J. J. Divoky. A Computational Study of Efficinet Shotest Path Algorithms. Comput. Ops. Res., 15:567\u2013576, 1988.","journal-title":"Comput. Ops. Res."},{"key":"26_CR15","unstructured":"J. L. Kennington and R. V. Helgason. Algorithms for Network Programming. John Wiley and Sons, 1980."},{"key":"26_CR16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1287\/mnsc.14.3.205","volume":"14","author":"M. Klein","year":"1967","unstructured":"M. Klein. A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems. Management Science, 14:205\u2013220, 1967.","journal-title":"Management Science"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"S.G. Kolliopoulos and C. Stein. Finding Real-Valued Single-Source Shortest Paths in o(n\n3) Expected Time. In Proc. 5th Int. Programming and Combinatorial Optimization Conf., 1996.","DOI":"10.1007\/3-540-61310-2_8"},{"key":"26_CR18","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E. L. Lawler","year":"1976","unstructured":"E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, NY, 1976."},{"key":"26_CR19","unstructured":"B. Ju. Levit and B. N. Livshits. Nelineinye Setevye Transportnye Zadachi. Transport, Moscow, 1972. In Russian."},{"key":"26_CR20","doi-asserted-by":"crossref","first-page":"767","DOI":"10.1016\/0305-0548(91)90014-I","volume":"18","author":"J-F. Mondou","year":"1991","unstructured":"J-F. Mondou, T.G. Crainic, and S. Nguyen. Shortest Path Algorithms: A Computational Study with the C Progremming Language. Computers and Oper. Res., 18:767\u2013786, 1991.","journal-title":"Computers and Oper. Res."},{"key":"26_CR21","unstructured":"E. F. Moore. The Shortest Path Through a Maze. In Proc. of the Int. Symp. on the Theory of Switching, pages 285\u2013292. Harvard University Press, 1959."},{"key":"26_CR22","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1002\/net.3230140206","volume":"14","author":"S. Pallottino","year":"1984","unstructured":"S. Pallottino. Shortest-Path Methods: Complexity, Interrelations and New Propositions. Networks, 14:257\u2013267, 1984.","journal-title":"Networks"},{"key":"26_CR23","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/BF01585517","volume":"7","author":"U. Pape","year":"1974","unstructured":"U. Pape. Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem. Math. Prog., 7:212\u2013222, 1974.","journal-title":"Math. Prog."},{"key":"26_CR24","unstructured":"P. Spirakis and A. Tsakadidis. A Very Fast, Practical Algorithm for Finding a Negative Cycle in a Digraph. In Proc. 13th ICALP, Lecture Notes in Computer Science 226, pages 59\u201367. Springer-Verlag, 1996."},{"key":"26_CR25","volume-title":"Technical report","author":"R. E. Tarjan","year":"1981","unstructured":"R. E. Tarjan. Shortest Paths. Technical report, AT&T Bell Laboratories, Murray Hill, NJ, 1981."},{"key":"26_CR26","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA '96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61680-2_67.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T21:35:25Z","timestamp":1619559325000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61680-2_67"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540616801","9783540706670"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-61680-2_67","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996]]}}}