{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T15:03:47Z","timestamp":1791299027745,"version":"4.1.0"},"reference-count":13,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5703,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1991,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We use Fibonacci heaps to improve a parametric shortest path algorithm of Karp and Orlin, and we combine our algorithm and the method of Schneider and Schneider's minimum\u2010balance algorithm to obtain a faster minimum\u2010balance algorithm.<\/jats:p><jats:p>For a graph with <jats:italic>n<\/jats:italic> vertices and <jats:italic>m<\/jats:italic> edges, our parametric shortest path algorithm and our minimum\u2010balance algorithm both run in <jats:italic>O<\/jats:italic>(<jats:italic>nm<\/jats:italic> + <jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup> log <jats:italic>n<\/jats:italic>) time, improved from <jats:italic>O<\/jats:italic>(<jats:italic>nm<\/jats:italic> log <jats:italic>n<\/jats:italic>) for the parametric shortest path algorithm of Karp and Orlin and <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup><jats:italic>m<\/jats:italic>) for the minimum\u2010balance algorithm of Schneider and Schneider.<\/jats:p><jats:p>An important application of the parametric shortest path algorithm is in finding a minimum mean cycle. Experiments on random graphs suggest that the expected time for finding a minimum mean cycle with our algorithm is <jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic> log <jats:italic>n<\/jats:italic> + <jats:italic>m<\/jats:italic>).<\/jats:p>","DOI":"10.1002\/net.3230210206","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T10:22:45Z","timestamp":1178965365000},"page":"205-221","source":"Crossref","is-referenced-by-count":119,"title":["Faster parametric shortest path and minimum\u2010balance algorithms"],"prefix":"10.1002","volume":"21","author":[{"given":"Neal E.","family":"Young","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjant","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James B.","family":"Orlin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"R. K.AhujaandJ. B.Orlin New scaling algorithms for assignment and minimum cycle mean problems. Sloan Working Paper 2019\u201088 Sloan School of Management M.I.T. (1988)."},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76368"},{"key":"e_1_2_1_5_2","volume-title":"Graphs and Algorithms","author":"Gondran M.","year":"1984"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230150107"},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0012-365X(78)90011-0","article-title":"A characterization of the minimum cycle mean in a digraph","volume":"23","author":"Karp R. M.","year":"1978","journal-title":"Discrete Math."},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90026-3"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585655"},{"key":"e_1_2_1_10_2","unstructured":"N.Schlenker personal communication Dept. of Computer Science Princeton University Princeton NJ (1989)."},{"key":"e_1_2_1_11_2","unstructured":"H.SchneiderandM. H.Schneider Max\u2010balancing weighted directed graphs. Unpublished manuscript University of Wisconsin (1987)."},{"key":"e_1_2_1_12_2","unstructured":"H.SchneiderandM. H.Schneider Towers and cycle covers for max\u2010balanced graphs. Unpublished manuscript University of Wisconsin (1989)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/322154.322161"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0606031"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230210206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230210206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T07:09:22Z","timestamp":1698044962000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230210206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,3]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1991,3]]}},"alternative-id":["10.1002\/net.3230210206"],"URL":"https:\/\/doi.org\/10.1002\/net.3230210206","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,3]]}}}