{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,5]],"date-time":"2026-11-05T22:04:19Z","timestamp":1793916259653,"version":"4.8.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1989,2]]},"abstract":"<jats:p>The classical maximum flow problem sometimes occurs in settings in which the arc capacities are not fixed but are functions of a single parameter, and the goal is to find the value of the parameter such that the corresponding maximum flow or minimum cut satisfies some side condition. Finding the desired parameter value requires solving a sequence of related maximum flow problems. In this paper it is shown that the recent maximum flow algorithm of Goldberg and Tarjan can be extended to solve an important class of such parametric maximum flow problems, at the cost of only a constant factor in its worst-case time bound. Faster algorithms for a variety of combinatorial optimization problems follow from the result.<\/jats:p>","DOI":"10.1137\/0218003","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:32:44Z","timestamp":1109226764000},"page":"30-55","source":"Crossref","is-referenced-by-count":427,"title":["A Fast Parametric Maximum Flow Algorithm and Applications"],"prefix":"10.1137","volume":"18","author":[{"given":"Giorgio","family":"Gallo","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael D.","family":"Grigoriadis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Tarjan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","unstructured":"R. K. Ahuja, J. B. Orlin,  A fast and simple algorithm for the maximum flow problem, Working Paper, 1905-87, Sloan School of Management, Massachusetts Institute of Technology, Cambridge, MA,  1987"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.3.230"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.2.324"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0083467"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3829"},{"key":"R6","first-page":"754","volume":"194","author":"Dinic E. A.","year":"1970","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.6028\/jres.069B.004"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/321978.321982"},{"key":"R10","volume-title":"Flows in networks","author":"Ford, Jr. L. R.","year":"1962"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120892"},{"key":"R12","unstructured":"A. V. Goldberg,  Finding a maximum density subgraph, Tech. Report, UCB CSD 84\/ 171, Computer Science Division (EELS), University of California, Berkeley, CA,  1984"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"R14","volume-title":"Graphs and algorithms","author":"Gondran Michel","year":"1984"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121089"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0307041"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322391"},{"key":"R18","unstructured":"D. Gusfield,  On scheduling transmissions in a network, Tech. Report, YALEU DCS TR 481, Department of Computer Science, Yale University, New Haven, CT,  1986"},{"key":"R19","unstructured":"D. Gusfield,  Computing the strength of a network in  O(|V|3|E|) time, Tech. Report, CSE-87-2, Department of Electrical and Computer Engineering, University of California, Davis, CA,  1987"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1137\/0216020"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01583798"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90010-0"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030108"},{"key":"R24","volume-title":"Combinatorial optimization: networks and matroids","author":"Lawler Eugene L.","year":"1976"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70323-6"},{"key":"R26","unstructured":"C. Martel,  A comparison of phase and non-phase network algorithms, Tech. Report, CSE-87-7, Department of Electrical and Computer Engineering, University of California, Davis, CA,  1987"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585506"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14298-5"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.4.414"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-39.1.12"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF02591725"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.22.11.1268"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"R34","first-page":"394","volume":"20","author":"Picard J. C.","year":"1982","journal-title":"INFOR"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230050405"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.3.200"},{"key":"R37","first-page":"149","volume":"6","author":"Ritter K.","year":"1962","journal-title":"Unter-nehmensforschung"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.22.8.868"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.2.283"},{"key":"R40","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(83)90006-5"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3835"},{"key":"R42","unstructured":"C. Stein,  Efficient algorithms for bipartite network flow,  1986, unpublished manuscript, Department of Computer Science, Princeton University, Princeton, NJ"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231502"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970265"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230130106"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0218003","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:43:38Z","timestamp":1787337818000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0218003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,2]]},"references-count":45,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,2]]}},"alternative-id":["10.1137\/0218003"],"URL":"https:\/\/doi.org\/10.1137\/0218003","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,2]]}}}