Abstract
We give an O(nd + nlogn) algorithm computing the number of minimum (s,t)-cuts in weighted planar graphs, where n is the number of vertices and d is the length of the shortest s-t path in the corresponding unweighted graph. Previously, Ball and Provan gave a polynomial-time algorithm for unweighted graphs with both s and t lying on the outer face. Our results hold for all locations of s and t and weighted graphs, and have direct applications in image segmentation and other computer vision problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ball, M.O., Provan, J.S.: Calculating Bounds on Reachability and Connectnedness in Stochastic Networks. Networks 13, 253–278 (1983)
Ball, M.O., Provan, J.S.: Computing Network Reliability in Time Polynomial in the Number of Cuts. Operations Research 32(3), 516–526 (1984)
Borradaile, G., Klein, P.: An O(n logn) algorithm for maximum st-flow in a directed planar graph. Journal of the ACM 56(2) (2009)
Boykov, Y., Kolmogorov, V.: An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Trans. Pattern Anal. Mach. Intell. 26(9), 1124–1137 (2004)
Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimisation via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence 29, 1222–1239 (2001)
Colbourn, C.J.: Combinatorial aspects of network reliability. Annals of Operations Research 33(1), 1–15 (2005)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2001)
Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics 8, 399–404 (1956)
Geman, D., Geman, S.: Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell. 6, 721–741 (1984)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. Journal of the ACM (JACM) 35(4), 921–940 (1988)
Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. Journal of the Association for Computing Machinery 21(4), 549–568 (1974)
Itai, A., Shiloach, Y.: Maximum Flow in Planar Networks. SIAM J. Comput. 8(2), 135–150 (1979)
Janiga, L., Koubek, V.: Minimum Cut in Directed Planar Networks. Kybernetika 28(1), 37–49 (1992)
Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43(2-3), 169–188 (1986)
Karger, D.R.: A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem. SIAM J. Comput. 29(2), 492–514 (1999)
Kleinberg, J., Tardos, É.: Algorithm Design. Addison Wesley, Reading (2005)
Nagamochi, H., Sun, Z., Ibaraki, T.: Counting the number of minimum cuts in undirected multigraphs. IEEE Transactions on Reliability 40(5), 610–614 (1991)
Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing probability that a graph is connected. SIAM J. Comput. 12(4), 777–788 (1983)
Ramanathan, A., Colbourn, C.J.: Counting almost minimum cutsets with reliability applications. Mathematical Programming 39(3), 253–261 (1987)
Reif, J.H.: Minimum s-t cut of a planar undirected network in O(n log2 n) time. SIAM Journal on Computing 12, 71–81 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bezáková, I., Friedlander, A.J. (2010). Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time. In: Hliněný, P., Kučera, A. (eds) Mathematical Foundations of Computer Science 2010. MFCS 2010. Lecture Notes in Computer Science, vol 6281. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15155-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-15155-2_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15154-5
Online ISBN: 978-3-642-15155-2
eBook Packages: Computer ScienceComputer Science (R0)