Skip to main content
SpringerLink
Log in

A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We present a new approach to the minimum-cost integral flow problem for small values of the flow. It reduces the problem to the tests of simple multivariate polynomials over a finite field of characteristic two for non-identity with zero. In effect, we show that a minimum-cost flow of value k in a network with n vertices, a sink and a source, integral edge capacities and positive integral edge costs polynomially bounded in n can be found by a randomized PRAM, with errors of exponentially small probability in n, running in O(klog(kn)+log2(kn)) time and using 2k(kn)O(1) processors. Thus, in particular, for the minimum-cost flow of value O(logn), we obtain an RNC2 algorithm, improving upon time complexity of earlier NC and RNC algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New York (1993)

    MATH  Google Scholar 

  2. 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–26 (1995)

    Article  Google Scholar 

  3. Björklund, A.: Determinant sums for undirected Hamiltonicity. In: Proceedings of the 51th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 173–182 (2010)

    Google Scholar 

  4. Björklund, A., Husfeldt, T., Taslaman, N.: Shortest Cycle Through Specified Elements. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1747–1753 (2012)

    Chapter  Google Scholar 

  5. DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7, 193–195 (1978)

    Article  MATH  Google Scholar 

  6. Edmonds, J.: Systems of distinct representatives and linear algebra. J. Res. Natl. Bur. Stand. 71B(4), 241–245 (1967)

    Article  MathSciNet  Google Scholar 

  7. Even, S.: Graph Algorithms. Computer Science (1979)

    MATH  Google Scholar 

  8. Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19(2), 248–264 (1972)

    Article  MATH  Google Scholar 

  9. Ford, L.R. Jr., Fulkerson, D.R.: Maximal flow through a network. Can. J. Math. 8, 399–404 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  10. Fulkerson, D.R.: An out-of-Kilter method for minimal cost flow problems. SIAM J. Appl. Math. 9, 18–27 (1961)

    Article  MATH  Google Scholar 

  11. Galil, Z., Pan, V.: Improved processor bounds for combinatorial problems in RNC. Combinatorica 8(2), 189–200 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  12. Goldberg, A.: Parallel algorithms for network flow problems. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms, Morgan Kaufmann, San Mateo (1993)

    Google Scholar 

  13. Goldschlager, L.M., Shaw, R.A., Staples, J.: The maximum flow problem is log space complete for P. Theor. Comput. Sci. 21(1), 105–111 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  14. JáJá, J.: An Introduction to Parallel Algorithms. Addison-Wesley, Reading (1992)

    MATH  Google Scholar 

  15. Karp, R., Upfal, E., Wigderson, A.: Constructing a perfect matching is in random NC. Combinatorica 6(1), 35–48 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  16. 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–586 (2008)

    Chapter  Google Scholar 

  17. Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1967)

    Google Scholar 

  18. Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as Easy as Matrix Inversion. Combinatorica 7(1), 105–113 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  19. Orlin, J.B., Stein, C.: Parallel Algorithms for the Assignment and Minimum-Cost Flow Problems. Oper. Res. Lett. 14, 181–186 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  20. Reif, J.H. (ed.): Synthesis of Parallel Algorithms. Morgan Kaufmann, San Mateo (1993)

    Google Scholar 

  21. Vazirani, V.V.: Parallel graph matching. In: Reif, J.H. (ed.) Synthesis of Parallel Algorithms. Morgan-Kaufmann, San Mateo (1993)

    Google Scholar 

  22. Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701–717 (1980)

    Article  MATH  Google Scholar 

  23. Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the Annual ACM Symposium on Theory of Computing (STOC), pp. 887–898 (2012)

    Google Scholar 

  24. Williams, R.: Finding paths of length k in O ∗(2k). Inf. Process. Lett. 109, 301–338 (2009)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, Lund University, 22100, Lund, Sweden

    Andrzej Lingas

  2. Department of Computer Science, Malmö University, 20506, Malmö, Sweden

    Mia Persson

Authors
  1. Andrzej Lingas
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mia Persson
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrzej Lingas.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lingas, A., Persson, M. A Fast Parallel Algorithm for Minimum-Cost Small Integral Flows. Algorithmica 72, 607–619 (2015). https://doi.org/10.1007/s00453-013-9865-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-013-9865-1

Keywords

Search

Navigation