{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:01:43Z","timestamp":1725562903901},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_13","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"126-137","source":"Crossref","is-referenced-by-count":0,"title":["Counting Minimum (s,t)-Cuts in Weighted Planar Graphs in Polynomial Time"],"prefix":"10.1007","author":[{"given":"Ivona","family":"Bez\u00e1kov\u00e1","sequence":"first","affiliation":[]},{"given":"Adam J.","family":"Friedlander","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/net.3230130210","volume":"13","author":"M.O. Ball","year":"1983","unstructured":"Ball, M.O., Provan, J.S.: Calculating Bounds on Reachability and Connectnedness in Stochastic Networks. Networks\u00a013, 253\u2013278 (1983)","journal-title":"Networks"},{"issue":"3","key":"13_CR2","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1287\/opre.32.3.516","volume":"32","author":"M.O. Ball","year":"1984","unstructured":"Ball, M.O., Provan, J.S.: Computing Network Reliability in Time Polynomial in the Number of Cuts. Operations Research\u00a032(3), 516\u2013526 (1984)","journal-title":"Operations Research"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Borradaile, G., Klein, P.: An O(n logn) algorithm for maximum st-flow in a directed planar graph. Journal of the ACM\u00a056(2) (2009)","DOI":"10.1145\/1502793.1502798"},{"issue":"9","key":"13_CR4","doi-asserted-by":"publisher","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","volume":"26","author":"Y. Boykov","year":"2004","unstructured":"Boykov, Y., Kolmogorov, V.: An Experimental Comparison of Min-Cut\/Max-Flow Algorithms for Energy Minimization in Vision. IEEE Trans. Pattern Anal. Mach. Intell.\u00a026(9), 1124\u20131137 (2004)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"13_CR5","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"29","author":"Y. Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimisation via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence\u00a029, 1222\u20131239 (2001)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"13_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF02061656","volume":"33","author":"C.J. Colbourn","year":"2005","unstructured":"Colbourn, C.J.: Combinatorial aspects of network reliability. Annals of Operations Research\u00a033(1), 1\u201315 (2005)","journal-title":"Annals of Operations Research"},{"key":"13_CR7","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2001)"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","volume":"8","author":"L.R. Ford","year":"1956","unstructured":"Ford, L.R., Fulkerson, D.R.: Maximal flow through a network. Canadian Journal of Mathematics\u00a08, 399\u2013404 (1956)","journal-title":"Canadian Journal of Mathematics"},{"key":"13_CR9","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","volume":"6","author":"D. Geman","year":"1984","unstructured":"Geman, D., Geman, S.: Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images. IEEE Trans. Pattern Anal. Mach. Intell.\u00a06, 721\u2013741 (1984)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"13_CR10","doi-asserted-by":"publisher","first-page":"921","DOI":"10.1145\/48014.61051","volume":"35","author":"A.V. Goldberg","year":"1988","unstructured":"Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum flow problem. Journal of the ACM (JACM)\u00a035(4), 921\u2013940 (1988)","journal-title":"Journal of the ACM (JACM)"},{"issue":"4","key":"13_CR11","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1145\/321850.321852","volume":"21","author":"J. Hopcroft","year":"1974","unstructured":"Hopcroft, J., Tarjan, R.E.: Efficient planarity testing. Journal of the Association for Computing Machinery\u00a021(4), 549\u2013568 (1974)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"13_CR12","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0208012","volume":"8","author":"A. Itai","year":"1979","unstructured":"Itai, A., Shiloach, Y.: Maximum Flow in Planar Networks. SIAM J. Comput.\u00a08(2), 135\u2013150 (1979)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR13","first-page":"37","volume":"28","author":"L. Janiga","year":"1992","unstructured":"Janiga, L., Koubek, V.: Minimum Cut in Directed Planar Networks. Kybernetika\u00a028(1), 37\u201349 (1992)","journal-title":"Kybernetika"},{"issue":"2-3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M.R. Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science\u00a043(2-3), 169\u2013188 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"13_CR15","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1137\/S0097539796298340","volume":"29","author":"D.R. Karger","year":"1999","unstructured":"Karger, D.R.: A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem. SIAM J. Comput.\u00a029(2), 492\u2013514 (1999)","journal-title":"SIAM J. Comput."},{"key":"13_CR16","volume-title":"Algorithm Design","author":"J. Kleinberg","year":"2005","unstructured":"Kleinberg, J., Tardos, \u00c9.: Algorithm Design. Addison Wesley, Reading (2005)"},{"issue":"5","key":"13_CR17","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1109\/24.106785","volume":"40","author":"H. Nagamochi","year":"1991","unstructured":"Nagamochi, H., Sun, Z., Ibaraki, T.: Counting the number of minimum cuts in undirected multigraphs. IEEE Transactions on Reliability\u00a040(5), 610\u2013614 (1991)","journal-title":"IEEE Transactions on Reliability"},{"issue":"4","key":"13_CR18","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"J.S. Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing probability that a graph is connected. SIAM J. Comput.\u00a012(4), 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"13_CR19","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BF02592076","volume":"39","author":"A. Ramanathan","year":"1987","unstructured":"Ramanathan, A., Colbourn, C.J.: Counting almost minimum cutsets with reliability applications. Mathematical Programming\u00a039(3), 253\u2013261 (1987)","journal-title":"Mathematical Programming"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1137\/0212005","volume":"12","author":"J.H. Reif","year":"1983","unstructured":"Reif, J.H.: Minimum s-t cut of a planar undirected network in O(n log2\n                n) time. SIAM Journal on Computing\u00a012, 71\u201381 (1983)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:33Z","timestamp":1606186893000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}