zbMATH — the first resource for mathematics

Flow in planar graphs with vertex capacities. (English) Zbl 0794.68114
Summary: Max-flow in planar graphs has always been studied with the assumption that there are capacities only on the edges. Here we consider a more general version of the problem when the vertices as well as edges have capacity constraints. In the context of general graphs considering only edge capacities is not restrictive, since the vertex-capacity problem can be reduced to the edge-capacity problem. However, in the case of planar graphs this reduction does not maintain planarity and cannot be used. We study different versions of the planar flow problem (all of which have been extensively investigated in the context of edge capacities).

68R10 Graph theory (including graph drawing) in computer science
90B10 Deterministic network models in operations research
Full Text: DOI
[1] Y. Birk and J. B. Lotspiech, A fast algorithm for connecting grid points to the boundary with nonintersecting straight lines,Proceedings of the second Symposium on Discrete Algorithms, pp. 465-474 (1991). · Zbl 0800.68470
[2] J. A. Bondy and U. S. R. Murty,Graph Theory with Applications, North-Holland, Amsterdam (1977). · Zbl 1226.05083
[3] T. H. Cormen, C. E. Leiserson, and R. L. Rivest,Introduction to Algorithms, MIT Press, Cambridge, MA (1990). · Zbl 1158.68538
[4] B. Codenetti and R. Tamassia, A network flow approach to reconfiguration of VLSI arrays,IEEE Transactions on Computers, Vol. 40, No. 1, pp. 118-121 (1991). · Zbl 05103534 · doi:10.1109/12.67329
[5] G. N. Frederickson, Fast algorithms for shortest paths in planar graphs, with applications,SIAM Journal on Computing, Vol. 16, pp. 1004-1022 (1987). · Zbl 0654.68087 · doi:10.1137/0216064
[6] L. R. Ford and D. R. Fulkerson, Maximal flow through a network,Canadian Journal of Mathematics, Vol. 8, pp. 399-404 (1956). · Zbl 0073.40203 · doi:10.4153/CJM-1956-045-5
[7] M. L. Fredman and D. E. Willard, Blasting through the information theoretic barrier with fusion trees,Proceedings of the 22nd Annual Symposium on Theory of Computing, pp. 1-7 (1990).
[8] J. W. Greene and A. El-Gamal, Configuration of VLSI arrays in the presence of defects,Journal of the ACM, Vol. 31, No. 4, pp. 694-717 (1984). · Zbl 0632.94033 · doi:10.1145/1634.2377
[9] R. E. Gomory and T. C. Hu, Multi-terminal network flows,SIAM Journal on Applied Mathematics, Vol. 9, pp. 551-570 (1961). · Zbl 0112.12405 · doi:10.1137/0109047
[10] F. Granot and R. Hassin, Multi-terminal maximum flows in node-capacitated networks,Discrete Applied Mathematics, Vol. 13, pp. 157-163 (1986). · Zbl 0607.90030 · doi:10.1016/0166-218X(86)90079-X
[11] L. Goldschlager, R. Shaw, and J. Staples, The maximum flow problem is log space complete forP, Theoretical Computer Science, Vol. 21, pp. 105-111 (1982). · Zbl 0486.68035 · doi:10.1016/0304-3975(82)90092-5
[12] A. V. Goldberg, E. Tardos, and R. E. Tarjan, Network flow algorithms, inPaths, Flows and VLSI-Layout (B. Korte, ed.), Springer-Verlag, New York, pp. 101-164 (1990).
[13] R. Hassin, Maximum flows in (s, t) planar networks,Information Processing Letters, Vol. 13, page 107 (1981). · doi:10.1016/0020-0190(81)90120-4
[14] R. Hassin and D. B. Johnson, An O(n log2 n) algorithm for maximum flow in undirected planar networks,SIAM Journal on Computing, Vol. 14, pp. 612-624 (1985). · Zbl 0565.90018 · doi:10.1137/0214045
[15] A. Itai and Y. Shiloach, Maximum flow in planar networks,SIAM Journal on Computing, Vol. 8, pp. 135-150 (1979). · Zbl 0419.90040 · doi:10.1137/0208012
[16] D. B. Johnson, Parallel algorithms for minimum cuts and maximum flows in planar networks,Journal of the ACM, Vol. 34, No. 4, pp. 950-967 (1987). · doi:10.1145/31846.31849
[17] D. B. Johnson and S. Venkatesan, Using divide and conquer to find flows in directed planar networks in O(n1.5 logn) time,Proceedings of the 20th Annual Allerton Conference on Communication, Control and Computing, University of Illinois, Urbana-Champaign, IL, pp. 898-905 (1982).
[18] S. Khuller and B. Schieber, Efficient parallel algorithms for testingk-connectivity and finding disjoints-t paths in graphs,SIAM Journal on Computing, Vol. 20, No. 2, pp. 352-375 (1991). · Zbl 0722.68066 · doi:10.1137/0220022
[19] R. J. Lipton, D. J. Rose, and R. E. Tarjan, Generalized nested dissection,SIAM Journal on Numerical Analysis, Vol. 16, pp. 346-358 (1979). · Zbl 0435.65021 · doi:10.1137/0716027
[20] G. L. Miller, Finding small simple separators for 2-connected planar graphs,Journal of Computer and System Sciences, Vol. 32, pp. 265-279 (1986). · Zbl 0607.05028 · doi:10.1016/0022-0000(86)90030-9
[21] G. L. Miller and J. Naor, Flow in planar graphs with multiple sources and sinks,Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pp. 112-117 (1989).
[22] T. Nishizeki and N. Chiba,Planar Graphs: Theory and Algorithms, Annals of Discrete Mathematics, Vol. 32, North-Holland, Amsterdam (1988). · Zbl 0647.05001
[23] V. Pan and J. H. Reif, Fast and efficient solution of path algebra problems,Journal of Computer and System Sciences, Vol. 38, No. 3, pp. 494-510 (1989). · Zbl 0682.68055 · doi:10.1016/0022-0000(89)90013-5
[24] J. H. Reif, Minimums-t cut of a planar undirected network in O(n log2 n) time,SIAM Journal on Computing, Vol. 12, No. 1, pp. 71-81 (1983). · Zbl 0501.68031 · doi:10.1137/0212005
[25] V. P. Roychowdhury and J. Bruck, On finding non-intersecting paths in a grid and its application in reconfiguration of VLSI/WSI arrays,Proceedings of the First Symposium on Discrete Algorithms, pp. 454-464 (1990). · Zbl 0800.68968
[26] V. P. Roychowdhury, J. Bruck, and T. Kailath, Efficient algorithms for reconfiguration in VLSI/WSI arrays,IEEE Transactions on Computers (Special Issue on Fault Tolerant Computing), Vol. 39, No. 4, pp. 480-489 (1990).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.