{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:14:00Z","timestamp":1763468040888},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642237188"},{"type":"electronic","value":"9783642237195"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-23719-5_14","type":"book-chapter","created":{"date-parts":[[2011,8,30]],"date-time":"2011-08-30T09:14:33Z","timestamp":1314695673000},"page":"155-166","source":"Crossref","is-referenced-by-count":8,"title":["Min-Cuts and Shortest Cycles in Planar Graphs in O(n loglogn) Time"],"prefix":"10.1007","author":[{"given":"Jakub","family":"\u0141\u0105cki","sequence":"first","affiliation":[]},{"given":"Piotr","family":"Sankowski","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica\u00a017, 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"14_CR2","first-page":"601","volume-title":"FOCS","author":"G. Borradaile","year":"2010","unstructured":"Borradaile, G., Sankowski, P., Wulff-Nilsen, C.: Min st-cut oracle for planar graphs with near-linear preprocessing time. In: FOCS, pp. 601\u2013610. IEEE Computer Society, Los Alamitos (2010)"},{"key":"14_CR3","first-page":"828","volume-title":"SODA","author":"P. Chalermsook","year":"2004","unstructured":"Chalermsook, P., Fakcharoenphol, J., Nanongkai, D.: A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In: Ian Munro, J. (ed.) SODA, pp. 828\u2013829. SIAM, Philadelphia (2004)"},{"issue":"3","key":"14_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D. Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. Journal of Graph Algorithms and Applications\u00a03(3), 1\u201327 (1999)","journal-title":"Journal of Graph Algorithms and Applications"},{"issue":"5","key":"14_CR5","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1016\/j.jcss.2005.05.007","volume":"72","author":"J. Fakcharoenphol","year":"2006","unstructured":"Fakcharoenphol, J., Rao, S.: Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci.\u00a072(5), 868\u2013889 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"14_CR6","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput.\u00a016(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Syst. Sci.\u00a055(1), 3\u201323 (1997)","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR8","unstructured":"Lu, H.-I., Chang, H.-C.: Subquadratic algorithm for dynamic shortest distances. In: COCOON (to appear, 2011)"},{"issue":"4","key":"14_CR9","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0207033","volume":"7","author":"A. Itai","year":"1978","unstructured":"Itai, A., Rodeh, M.: Finding a minimum circuit in a graph. SIAM J. Comput.\u00a07(4), 413\u2013423 (1978)","journal-title":"SIAM J. Comput."},{"key":"14_CR10","doi-asserted-by":"crossref","unstructured":"Italiano, G.F., Nussbaum, Y., Sankowski, P., Wulff-Nilsen, C.: Improved Min Cuts and Max Flows in Undirected Planar Graphs. In: STOC (2011)","DOI":"10.1145\/1993636.1993679"},{"issue":"1","key":"14_CR11","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1145\/331605.331608","volume":"47","author":"D.R. Karger","year":"2000","unstructured":"Karger, D.R.: Minimum cuts in near-linear time. Journal of the ACM (JACM)\u00a047(1), 46\u201376 (2000)","journal-title":"Journal of the ACM (JACM)"},{"key":"14_CR12","first-page":"146","volume-title":"SODA","author":"P.N. Klein","year":"2005","unstructured":"Klein, P.N.: Multiple-source shortest paths in planar graphs. In: SODA, pp. 146\u2013155. SIAM, Philadelphia (2005)"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/3-540-52921-7_51","volume-title":"Algorithms","author":"H. Nagamochi","year":"1990","unstructured":"Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multiple and capacitated graphs. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 12\u201320. Springer, Heidelberg (1990)"},{"key":"14_CR14","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/380752.380804","volume-title":"Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 2001","author":"M. Thorup","year":"2001","unstructured":"Thorup, M.: Fully-dynamic min-cut. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, STOC 2001, pp. 224\u2013230. ACM, New York (2001)"},{"issue":"2","key":"14_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1137\/S0895480194274133","volume":"10","author":"R. Yuster","year":"1997","unstructured":"Yuster, R., Zwick, U.: Finding even cycles even faster. SIAM J. Discrete Math.\u00a010(2), 209\u2013222 (1997)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2011"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-23719-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T12:03:19Z","timestamp":1554120199000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-23719-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642237188","9783642237195"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-23719-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}