Abstract
This paper presents efficient sequential and parallel algorithms for the minimum cost flow problem on planar networks. Our algorithms are based on the interior point method for linear programming, and make full use of the planarity of networks in solving a system of linear equations in sequential and parallel ways. For the planar minimum cost flow problem with n vertices and integer costs and capacities on edges whose absolute values are bounded by γ, we give a sequential algorithm with O(n 1.594 \(\sqrt {\log n}\)log(nγ)) time and O(nlogn) space and a parallel algorithm with O(\(\sqrt n\)log3 n log(nγ)) parallel time using O(n 1.094) processors. These algorithms are currently best for γ=poly(n). These results can be generalized to the minimum cost flow problem on s(n)-separable networks such as three-dimensional grid networks.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. P. Brent: The Parallel Evaluation of General Arithmetic Expressions. Journal of the Association for Computing Machinery, Vol.21, No.2 (1974), pp.201–206.
D. Coppersmith and S. Winograd: Matrix Multiplication via Arithmetic Progressions. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp.1–6.
G. N. Frederickson: Fast Algorithms for Shortest Paths in Planar Graphs, with Applications. SIAM Journal on Computing, Vol.16, No.6 (1987), pp.1004–1022.
H. Gazit and G. L. Miller: A Parallel Algorithm for Finding a Separator in Planar Graphs. Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, Los Angeles, 1987, pp.238–248.
A. George: Nested Dissection of a Regular Finite Element Mesh. SIAM Journal on Numerical Analysis, Vol.10, No.2 (1973), pp.345–363.
A. V. Goldberg, S. A. Plotkin, D. B. Shmoys and É. Tardos: Interior-Point Methods in Parallel Computation. Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp.350–355.
A. V. Goldberg and R. E. Tarjan: Solving Minimum Cost Flow Problems by Successive Approximation. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, pp.7–18.
R. J. Lipton, D. J. Rose, and R. E. Tarjan: Generalized Nested Dissection. SIAM Journal on Numerical Analysis, Vol.16, No.2 (1979), pp.346–358.
R. J. Lipton and R. E. Tarjan: A Separator Theorem for Planar Graphs. SIAM Journal on Applied Mathematics, Vol.36, No.2 (1979), pp.177–189.
J. B. Orlin: A Faster Strongly Polynomial Minimum Cost Flow Algorithm. Proceedings of the 20th Annual ACM Symposium on Theory of Computing, 1988, pp.377–387.
V. Pan: Fast and Efficient Parallel Algorithms for Exact Inversion of Integer Matrices. Proceedings of the 5th Conference on Foundations of Software Technology and Theoretical Computer Science, New Delhi, India, Lecture Notes in Computer Science 206 (Springer, Berlin, 1985), pp.504–521.
V. Pan and J. Reif: Efficient Parallel Solution of Linear Systems. Proceedings of the 17th Annual ACM Symposium on Theory of Computing, Providence, 1985, pp.143–152.
P. Vaidya: Speeding-Up Linear Programming Using Fast Matrix Multiplication. Proceeding of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp.332–337.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Imai, H., Iwano, K. (1990). Efficient sequential and parallel algorithms for planar minimum cost flow. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_52
Download citation
DOI: https://doi.org/10.1007/3-540-52921-7_52
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52921-7
Online ISBN: 978-3-540-47177-6
eBook Packages: Springer Book Archive