{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T10:15:25Z","timestamp":1672568125819},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[1998,9]]},"abstract":"We conduct a computational study of unit capacity flow and bipartite matching algorithms. Our goal is to determine which variant of the push-relabel method is most efficient in practice and to compare push-relabel algorithms with augmenting path algorithms. We have implemented and compared three push-relabel algorithms, three augmenting-path algorithms (one of which is new), and one augment-relabel algorithm. The depth-first search augmenting path algorithm was thought to be a good choice for the bipartite matching problem, but our study shows that it is not robust (meaning that it is not consistently fast on all or most inputs). For the problems we study, our implementations of the FIFO and lowest-level selection push-relabel algorithms have the most robust asymptotic rate of growth and work best overall. Augmenting path algorithms, although not as robust, on some problem classes are faster by a moderate constant factor. Our study includes several new problem families and input graphs with as many as 5 \u00d7 10<sup>5<\/sup> vertices.<\/jats:p>","DOI":"10.1145\/297096.297140","type":"journal-article","created":{"date-parts":[[2005,8,2]],"date-time":"2005-08-02T06:34:09Z","timestamp":1122964449000},"page":"8","source":"Crossref","is-referenced-by-count":27,"title":["Augment or push"],"prefix":"10.1145","volume":"3","author":[{"given":"Boris V.","family":"Cherkassky","sequence":"first","affiliation":[{"name":"Central Institute for Economics"}]},{"given":"Andrew V.","family":"Goldberg","sequence":"additional","affiliation":[{"name":"NEC Research Institute"}]},{"given":"Paul","family":"Martin","sequence":"additional","affiliation":[{"name":"NEC Research Institute"}]},{"given":"Joao C.","family":"Setubal","sequence":"additional","affiliation":[{"name":"Univ. of Campinas (Brazil)"}]},{"given":"Jorge","family":"Stolfi","sequence":"additional","affiliation":[{"name":"Univ. of Campinas (Brazil)"}]}],"member":"320","published-online":{"date-parts":[[1998,9]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja R. K.","year":"1993","unstructured":"{1} R. K. Ahuja , T. L. Magnanti , and J. B. Orlin . Network Flows: Theory, Algorithms, and Applications . Prentice-Hall , 1993 . {1} R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, 1993."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791199334"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90195-N"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/012\/01"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940880"},{"key":"e_1_2_2_7_1","series-title":"Collected Papers","first-page":"90","volume-title":"Combinatorial Methods for Flow Problems","author":"Cherkassky B. V.","year":"1979","unstructured":"{7} B. V. Cherkassky . A Fast Algorithm for Computing Maximum Flow in a Network . In A. V. Karzanov, editor, Collected Papers , Vol. 3 : Combinatorial Methods for Flow Problems , pages 90 - 96 . The Institute for Systems Studies , Moscow , 1979 . In Russian. English translation appears in AMS Trans., Vol. 158, pp. 23-30, 1994. {7} B. V. Cherkassky. A Fast Algorithm for Computing Maximum Flow in a Network. In A. V. Karzanov, editor, Collected Papers, Vol. 3: Combinatorial Methods for Flow Problems, pages 90-96. The Institute for Systems Studies, Moscow, 1979. In Russian. English translation appears in AMS Trans., Vol. 158, pp. 23-30, 1994."},{"key":"e_1_2_2_10_1","volume-title":"Implementing Goldberg's Max-Flow Algorithm - A Computational Investigation. ZOR - Methods and Models of Operations Research, 33:383-403","author":"Derigs U.","year":"1989","unstructured":"{10} U. Derigs and W. Meier . Implementing Goldberg's Max-Flow Algorithm - A Computational Investigation. ZOR - Methods and Models of Operations Research, 33:383-403 , 1989 . {10} U. Derigs and W. Meier. Implementing Goldberg's Max-Flow Algorithm - A Computational Investigation. ZOR - Methods and Models of Operations Research, 33:383-403, 1989."},{"key":"e_1_2_2_11_1","first-page":"209","volume-title":"ASI Series on Computer and System Sciences","author":"Derigs U.","year":"1992","unstructured":"{11} U. Derigs and W. Meier . An Evaluation of Algorithmic Refinements and Proper Data-Structures for the Preflow-Push Approach for Maximum Flow . In ASI Series on Computer and System Sciences , volume 8 , pages 209 - 223 . NATO , 1992 . {11} U. Derigs and W. Meier. An Evaluation of Algorithmic Refinements and Proper Data-Structures for the Preflow-Push Approach for Maximum Flow. In ASI Series on Computer and System Sciences, volume 8, pages 209-223. NATO, 1992."},{"key":"e_1_2_2_12_1","first-page":"1277","article-title":"Algorithm for Solution of a Problem of Maximum Flow","volume":"11","author":"Dinic E. A.","year":"1970","unstructured":"{12} E. A. Dinic . Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl. , 11 : 1277 - 1280 , 1970 . {12} E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl., 11:1277-1280, 1970.","journal-title":"Networks with Power Estimation. Soviet Math. Dokl."},{"key":"e_1_2_2_13_1","first-page":"507","volume":"4","author":"Even S.","year":"1975","unstructured":"{13} S. Even and R. E. Tarjan . Network Flow and Testing Graph Connectivity. SIAM J. Comput. , 4 : 507 - 518 , 1975 . {13} S. Even and R. E. Tarjan. Network Flow and Testing Graph Connectivity. SIAM J. Comput., 4:507-518, 1975.","journal-title":"Network Flow and Testing Graph Connectivity. SIAM J. Comput."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103424"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585996"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1009"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12144"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.61051"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288321"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_2_23_1","volume-title":"Matematicheskie Voprosy Upravleniya Proizvodstvom","author":"Karzanov A. V.","year":"1973","unstructured":"{23} A. V. Karzanov . O nakhozhdenii maksimal'nogo potoka v setyakh spetsial'nogo vida i nekotorykh prilozheniyakh . In Matematicheskie Voprosy Upravleniya Proizvodstvom , volume 5 . Moscow State University Press , Moscow , 1973 . In Russian; title translation: On Finding Maximum Flows in Networks with Special Structure and Some Applications. {23} A. V. Karzanov. O nakhozhdenii maksimal'nogo potoka v setyakh spetsial'nogo vida i nekotorykh prilozheniyakh. In Matematicheskie Voprosy Upravleniya Proizvodstvom, volume 5. Moscow State University Press, Moscow, 1973. In Russian; title translation: On Finding Maximum Flows in Networks with Special Structure and Some Applications."},{"key":"e_1_2_2_24_1","first-page":"66","volume-title":"Problems in Cibernetics","author":"Karzanov A. V.","year":"1973","unstructured":"{24} A. V. Karzanov . Tochnaya otzenka algoritma nakhojdeniya maksimalnogo potoka, primenennogo k zadache \"o predstavitelyakh \". In Problems in Cibernetics , volume 5 , pages 66 - 70 . Nauka, Moscow , 1973 . In Russian; title translation: The exact time bound for a maximum flow algorithm applied to the set representatives problem. {24} A. V. Karzanov. Tochnaya otzenka algoritma nakhojdeniya maksimalnogo potoka, primenennogo k zadache \"o predstavitelyakh\". In Problems in Cibernetics, volume 5, pages 66-70. Nauka, Moscow, 1973. In Russian; title translation: The exact time bound for a maximum flow algorithm applied to the set representatives problem."},{"key":"e_1_2_2_26_1","volume-title":"Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston","author":"Lawler E. L.","year":"1976","unstructured":"{26} E. L. Lawler . Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston , New York, NY ., 1976 . {26} E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Reinhart, and Winston, New York, NY., 1976."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/012\/02"},{"key":"e_1_2_2_28_1","first-page":"211","volume-title":"Setubal. New Experimental Results for Bipartite Matching. In Proceedings of NETFLOW 93","author":"J.","year":"1993","unstructured":"{28} J. C. Setubal. New Experimental Results for Bipartite Matching. In Proceedings of NETFLOW 93 , pages 211 - 216 . TR-21\/93, Dipartimento di Informatica, Universit\u00e1 di Pisa , 1993 . {28} J. C. Setubal. New Experimental Results for Bipartite Matching. In Proceedings of NETFLOW 93, pages 211-216. TR-21\/93, Dipartimento di Informatica, Universit\u00e1 di Pisa, 1993."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/297096.297140","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T10:42:07Z","timestamp":1672483327000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/297096.297140"}},"subtitle":["a computational study of bipartite matching and unit-capacity flow algorithms"],"short-title":[],"issued":{"date-parts":[[1998,9]]},"references-count":22,"alternative-id":["10.1145\/297096.297140"],"URL":"http:\/\/dx.doi.org\/10.1145\/297096.297140","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"value":"1084-6654","type":"print"},{"value":"1084-6654","type":"electronic"}],"subject":["Theoretical Computer Science"],"published":{"date-parts":[[1998,9]]}}}