{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T11:18:40Z","timestamp":1720696720510},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1-4","license":[{"start":{"date-parts":[[1989,6,1]],"date-time":"1989-06-01T00:00:00Z","timestamp":612662400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1989,6]]},"DOI":"10.1007\/bf01553885","type":"journal-article","created":{"date-parts":[[2005,4,20]],"date-time":"2005-04-20T22:07:35Z","timestamp":1114034855000},"page":"173-189","source":"Crossref","is-referenced-by-count":4,"title":["On the efficiency of maximum-flow algorithms on networks with small integer capacities"],"prefix":"10.1007","volume":"4","author":[{"given":"David","family":"Fern\u00e1ndez-Baca","sequence":"first","affiliation":[]},{"given":"Charles U.","family":"Martel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF01553885_CR1","first-page":"117","volume":"7","author":"B. Cherkaski","year":"1977","unstructured":"Cherkaski, B. Algorithm for construction of maximal flow in networks with complexityO(\u00a6V\u00a62\u00a6E\u00a61\/2) operations.Math. Methods Solutions Econ. Problems 7 (1977), 117\u2013125 (in Russian\u2014see also [GALI80]).","journal-title":"Math. Methods Solutions Econ. Problems"},{"key":"BF01553885_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/355873.355874","volume":"6","author":"T. Cheung","year":"1980","unstructured":"Cheung, T. Computational comparison of eight methods for the maximum flow problem.ACM Trans. Math. Software 6 (1980), 1\u201316.","journal-title":"ACM Trans. Math. Software"},{"key":"BF01553885_CR3","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 a network with power estimation.Soviet Math. Dokl. 11 (1970), 1277\u20131280.","journal-title":"Soviet Math. Dokl."},{"key":"BF01553885_CR4","doi-asserted-by":"crossref","first-page":"507","DOI":"10.1137\/0204043","volume":"4","author":"S. Even","year":"1975","unstructured":"Even, S., and Tarjan, R. E. Network flow and testing graph connectivity.SIAM J. Comput. 4 (1975), 507\u2013518.","journal-title":"SIAM J. Comput."},{"key":"BF01553885_CR5","volume-title":"Ph.D. Dissertation","author":"D. Fern\u00e1ndez-Baca","year":"1986","unstructured":"Fern\u00e1ndez-Baca, D. Improved Bounds on Network Flow Algorithms with Applications. Ph.D. Dissertation, Computer Science Division, University of California, Davis, CA, 1986."},{"key":"BF01553885_CR6","doi-asserted-by":"crossref","unstructured":"Gabow, H. N. Scaling algorithms for network problems.Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, 1983, pp. 248\u2013257.","DOI":"10.1109\/SFCS.1983.68"},{"key":"BF01553885_CR7","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF00264254","volume":"14","author":"Z. Galil","year":"1980","unstructured":"Galil, Z. AnO(V 5\/3 E 2\/3) algorithm for the maximal flow problem.Acta Inform. 14 (1980), 221\u2013242.","journal-title":"Acta Inform."},{"key":"BF01553885_CR8","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0022-0000(80)90035-5","volume":"21","author":"Z. Galil","year":"1980","unstructured":"Galil, Z., and Naamad, A. AnO(EV log2 V) algorithm for the maximal flow problem.J. Comput. System Sci. 21 (1980), 203\u2013217.","journal-title":"J. Comput. System Sci."},{"key":"BF01553885_CR9","series-title":"Technical Report LCSR-TR-95","volume-title":"A fast parametric minimum cut algorithm","author":"G. Gallo","year":"1986","unstructured":"Gallo, G., Grigoriades, M., and Tarjan, R. A fast parametric minimum cut algorithm. Technical Report LCSR-TR-95, Department of Computer Science, Rutgers University, New Brunswick, NJ, November 1986."},{"key":"BF01553885_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1137\/0216020","volume":"16","author":"D. Gusfield","year":"1987","unstructured":"Gusfield, D., Martel, C. U., and Fern\u00e1ndez-Baca, D. Fast algorithms for bipartite network flow.SIAM J. Comput. 16 (1987), 237\u2013251.","journal-title":"SIAM J. Comput."},{"key":"BF01553885_CR11","volume-title":"Ph.D. Dissertation","author":"A. V. Goldberg","year":"1987","unstructured":"Goldberg, A. V. Dfficient Algorithms for Sequential and Parallel Computers. Ph.D. Dissertation, EECSS Department, Massachusetts Institute of Technology, Cambridge, MA, January 1987."},{"key":"BF01553885_CR12","doi-asserted-by":"crossref","unstructured":"Goldberg, A. V., and Tarjan, R. E. A new approach to the maximum flow problem.Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 136\u2013146.","DOI":"10.1145\/12130.12144"},{"key":"BF01553885_CR13","first-page":"434","volume":"15","author":"A. V. Karzanov","year":"1974","unstructured":"Karzanov, A. V. Determining the maximal flow in a network by the method of preflows.Soviet Math. Dokl. 15 (1974), 434\u2013437.","journal-title":"Soviet Math. Dokl."},{"key":"BF01553885_CR14","series-title":"Technical Report CSE-87-7","volume-title":"A Comparison of Phase and Non-Phase Network Flow Algorithms","author":"C. U. Martel","year":"1987","unstructured":"Martel, C. U. A Comparison of Phase and Non-Phase Network Flow Algorithms. Technical Report CSE-87-7, Computer Science Division, University of California, Davis, CA, June 1987."},{"key":"BF01553885_CR15","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/0020-0190(78)90016-9","volume":"7","author":"V. Malhotra","year":"1978","unstructured":"Malhotra, V., Pramod Kumar, M., and Maheshwari, S. AnO(\u00a6V\u00a63) algorithm for finding maximum flows in networks.Inform. Process. Lett. 7 (1978), 277\u2013278.","journal-title":"Inform. Process. Lett."},{"key":"BF01553885_CR16","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"C. H. Papadimitriou","year":"1982","unstructured":"Papadimitriou, C. H., and Steiglitz, K.Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, NJ, 1982."},{"key":"BF01553885_CR17","first-page":"394","volume":"20","author":"J. Picard","year":"1982","unstructured":"Picard, J., and Queyranne, M. Selected Applications of Minimum Cuts in Networks.INFOR 20 (1982), 394\u2013422.","journal-title":"INFOR"},{"key":"BF01553885_CR18","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1002\/net.3230120206","volume":"12","author":"J. Picard","year":"1982","unstructured":"Picard, J., and Queyranne, M. A network flow solution to some non-linear 0-1 programming problems with applications to graph theory.Networks 12 (1982), 141\u2013159.","journal-title":"Networks"},{"key":"BF01553885_CR19","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"D. D. Sleator","year":"1983","unstructured":"Sleator, D. D., and Tarjan, R. E. A data structure for dynamic trees.J. Comput. System Sci. 26 (1983), 362\u2013391.","journal-title":"J. Comput. System Sci."},{"key":"BF01553885_CR20","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611970265","volume-title":"Data Structures and Network Algorithms","author":"R. E. Tarjan","year":"1983","unstructured":"Tarjan, R. E.Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553885.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01553885\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01553885","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,3]],"date-time":"2019-05-03T14:21:13Z","timestamp":1556893273000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01553885"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,6]]},"references-count":20,"journal-issue":{"issue":"1-4","published-print":{"date-parts":[[1989,6]]}},"alternative-id":["BF01553885"],"URL":"https:\/\/doi.org\/10.1007\/bf01553885","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,6]]}}}