{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:35:38Z","timestamp":1774946138737,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540388753","type":"print"},{"value":"9783540388760","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_55","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"612-623","source":"Crossref","is-referenced-by-count":8,"title":["Balancing Applied to Maximum Network Flow Problems"],"prefix":"10.1007","author":[{"given":"Robert","family":"Tarjan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julie","family":"Ward","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunhong","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jia","family":"Mao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"55_CR1","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1137\/0218065","volume":"18","author":"R.K. Ahuja","year":"1989","unstructured":"Ahuja, R.K., Orlin, J.B., Tarjan, R.E.: Improved time bounds for the maximum flow problem. SIAM Journal on Computing\u00a018, 939\u2013954 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"55_CR2","first-page":"459","volume-title":"Proc. FOCS","author":"B. Awerbuch","year":"1993","unstructured":"Awerbuch, B., Leighton, F.T.: A simple local-control approximation algorithm for multicommodity flow. In: Proc. FOCS, pp. 459\u2013468. IEEE, Los Alamitos (1993)"},{"key":"55_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Leighton, T.: Improved approximation algorithms for the multi-commodity flow problem and local competitive routing in dynamic networks. In: STOC, pp. 487\u2013496 (1994)","DOI":"10.1145\/195058.195238"},{"issue":"3","key":"55_CR4","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1287\/mnsc.17.3.230","volume":"17","author":"M.L. Balinski","year":"1970","unstructured":"Balinski, M.L.: On a selection problem. Management Science\u00a017(3), 230\u2013231 (1970)","journal-title":"Management Science"},{"issue":"4","key":"55_CR5","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1016\/S0022-0000(73)80033-9","volume":"7","author":"M. Blum","year":"1973","unstructured":"Blum, M., Floyd, R.W., Pratt, V.R., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences\u00a07(4), 448\u2013461 (1973)","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"55_CR6","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/PL00009180","volume":"19","author":"B.V. Cherkassky","year":"1997","unstructured":"Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica\u00a019(4), 390\u2013410 (1997)","journal-title":"Algorithmica"},{"key":"55_CR7","first-page":"1277","volume":"11","author":"E.A. Dinic","year":"1970","unstructured":"Dinic, E.A.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl.\u00a011, 1277\u20131280 (1970)","journal-title":"Soviet Math. Dokl."},{"issue":"4","key":"55_CR8","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/321978.321982","volume":"23","author":"M.J. Eisner","year":"1976","unstructured":"Eisner, M.J., Severance, D.G.: Mathematical techniques for efficient record segmentation in shared databases. Journal of the ACM\u00a023(4), 619\u2013635 (1976)","journal-title":"Journal of the ACM"},{"issue":"4","key":"55_CR9","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1080\/15427951.2004.10129093","volume":"1","author":"G.W. Flake","year":"2005","unstructured":"Flake, G.W., Tarjan, R.E., Tsioutsiouliklis, K.: Graph clustering and minimum cut trees. Internet Mathematics\u00a01(4), 385\u2013408 (2005)","journal-title":"Internet Mathematics"},{"key":"55_CR10","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1016\/S0167-6377(02)00237-7","volume":"31","author":"S. Fujishige","year":"2003","unstructured":"Fujishige, S.: A maximum flow algorithm using MA ordering. Operations Research Letters\u00a031, 176\u2013178 (2003)","journal-title":"Operations Research Letters"},{"issue":"1","key":"55_CR11","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"Gallo, G., Grigoriadis, M.D., Tarjan, R.E.: A fast parametric maximum flow algorithm and applications. SIAM J. Computing\u00a018(1), 30\u201355 (1989)","journal-title":"SIAM J. Computing"},{"key":"55_CR12","unstructured":"Goldberg, A.: Private communication (2006)"},{"issue":"4","key":"55_CR13","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A. Goldberg","year":"1988","unstructured":"Goldberg, A., Tarjan, R.: A new approach to the maximum flow problem. Journal of the ACM\u00a035(4), 921\u2013940 (1988)","journal-title":"Journal of the ACM"},{"issue":"5","key":"55_CR14","doi-asserted-by":"publisher","first-page":"783","DOI":"10.1145\/290179.290181","volume":"45","author":"A.V. Goldberg","year":"1998","unstructured":"Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. Journal of the ACM\u00a045(5), 783\u2013797 (1998)","journal-title":"Journal of the ACM"},{"key":"55_CR15","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/BF01758775","volume":"7","author":"D. Gusfield","year":"1992","unstructured":"Gusfield, D., Martel, C.: A fast algorithm for the generalized parametric minimum cut problem and applications. Algorithmica\u00a07, 499\u2013519 (1992)","journal-title":"Algorithmica"},{"issue":"6","key":"55_CR16","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1287\/mnsc.1040.0242","volume":"50","author":"D. Hochbaum","year":"2004","unstructured":"Hochbaum, D.: Selection, provisioning, shared fixed costs, maximum closure, and implications on algorithmic methods today. Management Science\u00a050(6), 709\u2013723 (2004)","journal-title":"Management Science"},{"issue":"11","key":"55_CR17","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1287\/mnsc.28.11.1328","volume":"28","author":"J. Mamer","year":"1982","unstructured":"Mamer, J., Smith, S.: Optimizing field repair kits based on job completion rate. Management Science\u00a028(11), 1328\u20131333 (1982)","journal-title":"Management Science"},{"key":"55_CR18","first-page":"297","volume":"48","author":"Y. Matsuoka","year":"2005","unstructured":"Matsuoka, Y., Fujishige, S.: Practical efficiency of maximum flow algorithms using MA orderings and preflows. J. Oper. Res. Soc. of Japan\u00a048, 297\u2013307 (2005)","journal-title":"J. Oper. Res. Soc. of Japan"},{"key":"55_CR19","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1287\/opre.47.5.744","volume":"47","author":"S.T. McCormick","year":"1999","unstructured":"McCormick, S.T.: Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Operations Research\u00a047, 744\u2013756 (1999)","journal-title":"Operations Research"},{"key":"55_CR20","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1093\/bioinformatics\/bti1054","volume":"21","author":"E. Nabieva","year":"2005","unstructured":"Nabieva, E., Jim, K., Agarwal, A., Chazelle, B., Singh, M.: Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics\u00a021, i302\u2013i310 (2005)","journal-title":"Bioinformatics"},{"issue":"3","key":"55_CR21","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/mnsc.17.3.200","volume":"17","author":"J.M.W. Rhys","year":"1970","unstructured":"Rhys, J.M.W.: A selection problem of shared fixed costs and network flows. Management Science\u00a017(3), 200\u2013207 (1970)","journal-title":"Management Science"},{"issue":"1","key":"55_CR22","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D.D. Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. Journal of Computer and System Sciences\u00a026(1), 362\u2013391 (1983)","journal-title":"Journal of Computer and System Sciences"},{"key":"55_CR23","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1109\/TSE.1978.231502","volume":"4","author":"H. Stone","year":"1978","unstructured":"Stone, H.: Critical load factors in two-processor distributed systems. IEEE Trans. Software Engineering\u00a04, 254\u2013258 (1978)","journal-title":"IEEE Trans. Software Engineering"},{"key":"55_CR24","unstructured":"Zhang, B., Ward, J., Feng, Q.: A simultaneous parametric maximum flow algorithm for finding the complete chain of solutions. Technical report, HP Labs (2004), \n                    \n                      http:\/\/www.hpl.hp.com\/techreports\/2004\/HPL-2004-189.html"},{"key":"55_CR25","unstructured":"Zhang, B., Ward, J., Feng, Q.: Simultaneous parametric maximum flow algorithm with vertex balancing. Technical report, HP Labs (2005), \n                    \n                      http:\/\/www.hpl.hp.com\/techreports\/2005\/HPL-2005-121.html"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_55.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:16:57Z","timestamp":1619507817000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_55"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/11841036_55","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}