{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,30]],"date-time":"2025-08-30T17:14:40Z","timestamp":1756574080556},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,1,10]],"date-time":"2014-01-10T00:00:00Z","timestamp":1389312000000},"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":[[2015,6]]},"DOI":"10.1007\/s00453-013-9865-1","type":"journal-article","created":{"date-parts":[[2014,1,9]],"date-time":"2014-01-09T12:22:11Z","timestamp":1389270131000},"page":"607-619","source":"Crossref","is-referenced-by-count":3,"title":["A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows"],"prefix":"10.1007","volume":"72","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[]},{"given":"Mia","family":"Persson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,1,10]]},"reference":[{"key":"9865_CR1","volume-title":"Network Flows: Theory, Algorithms, and Applications","author":"R.K. Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New York (1993)"},{"issue":"1","key":"9865_CR2","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1006\/jpdc.1995.1103","volume":"29","author":"R.J. Anderson","year":"1995","unstructured":"Anderson, R.J., Setubal, J.C.: A parallel implementation of the push-relabel algorithm for the maximum flow problem. J. Parallel Distrib. Comput. 29(1), 17\u201326 (1995)","journal-title":"J. Parallel Distrib. Comput."},{"key":"9865_CR3","first-page":"173","volume-title":"Proceedings of the 51th IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Determinant sums for undirected Hamiltonicity. In: Proceedings of the 51th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 173\u2013182 (2010)"},{"key":"9865_CR4","doi-asserted-by":"crossref","first-page":"1747","DOI":"10.1137\/1.9781611973099.139","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"A. Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Taslaman, N.: Shortest Cycle Through Specified Elements. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1747\u20131753 (2012)"},{"key":"9865_CR5","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R.A. DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7, 193\u2013195 (1978)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9865_CR6","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","volume":"71B","author":"J. Edmonds","year":"1967","unstructured":"Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bur. Stand. 71B(4), 241\u2013245 (1967)","journal-title":"J. Res. Natl. Bur. Stand."},{"key":"9865_CR7","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"Even, S.: Graph Algorithms. Computer Science (1979)"},{"issue":"2","key":"9865_CR8","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248\u2013264 (1972)","journal-title":"J. ACM"},{"key":"9865_CR9","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford Jr.","year":"1956","unstructured":"Ford, L.R. Jr., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399\u2013404 (1956)","journal-title":"Can. J. Math."},{"key":"9865_CR10","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1137\/0109002","volume":"9","author":"D.R. Fulkerson","year":"1961","unstructured":"Fulkerson, D.R.: An out-of-Kilter method for minimal cost flow problems. SIAM J. Appl. Math. 9, 18\u201327 (1961)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"9865_CR11","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02122800","volume":"8","author":"Z. Galil","year":"1988","unstructured":"Galil, Z., Pan, V.: Improved processor bounds for combinatorial problems in RNC. Combinatorica 8(2), 189\u2013200 (1988)","journal-title":"Combinatorica"},{"key":"9865_CR12","volume-title":"Synthesis of Parallel Algorithms","author":"A. Goldberg","year":"1993","unstructured":"Goldberg, A.: Parallel algorithms for network flow problems. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms, Morgan Kaufmann, San Mateo (1993)"},{"issue":"1","key":"9865_CR13","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L.M. Goldschlager","year":"1982","unstructured":"Goldschlager, L.M., Shaw, R.A., Staples, J.: The maximum flow problem is log space complete for P. Theor. Comput. Sci. 21(1), 105\u2013111 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"9865_CR14","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)"},{"issue":"1","key":"9865_CR15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","volume":"6","author":"R. Karp","year":"1986","unstructured":"Karp, R., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6(1), 35\u201348 (1986)","journal-title":"Combinatorica"},{"key":"9865_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/978-3-540-70575-8_47","volume-title":"Proceedings of the 35th Annual International Colloquium on Automata, Languages and Programming (ICALP)","author":"I. Koutis","year":"2008","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Proceedings of the 35th Annual International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5125, pp. 575\u2013586 (2008)"},{"key":"9865_CR17","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"E.L. Lawler","year":"1967","unstructured":"Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1967)"},{"issue":"1","key":"9865_CR18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as Easy as Matrix Inversion. Combinatorica 7(1), 105\u2013113 (1987)","journal-title":"Combinatorica"},{"key":"9865_CR19","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0167-6377(93)90068-R","volume":"14","author":"J.B. Orlin","year":"1993","unstructured":"Orlin, J.B., Stein, C.: Parallel Algorithms for the Assignment and Minimum-Cost Flow Problems. Oper. Res. Lett. 14, 181\u2013186 (1993)","journal-title":"Oper. Res. Lett."},{"volume-title":"Synthesis of Parallel Algorithms","year":"1993","key":"9865_CR20","unstructured":"Reif, J.H. (ed.): Synthesis of Parallel Algorithms. Morgan Kaufmann, San Mateo (1993)"},{"key":"9865_CR21","volume-title":"Synthesis of Parallel Algorithms","author":"V.V. Vazirani","year":"1993","unstructured":"Vazirani, V.V.: Parallel graph matching. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms. Morgan-Kaufmann, San Mateo (1993)"},{"issue":"4","key":"9865_CR22","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"9865_CR23","first-page":"887","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC)","author":"V. Vassilevska Williams","year":"2012","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 887\u2013898 (2012)"},{"key":"9865_CR24","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R. Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in O \u2217(2 k ). Inf. Process. Lett. 109, 301\u2013338 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9865-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9865-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9865-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:13Z","timestamp":1559123113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9865-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1,10]]},"references-count":24,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["9865"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9865-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2014,1,10]]}}}