2026-07-24T06:08:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3004 2024-03-06T10:33:43Z ddc:004 open_access

Minimum s-t cut in undirected planar graphs when the source and the sink are close Kaplan, Haim Nussbaum, Yahav planar graph minimum cut shortest path cut cycle Consider the minimum s-t cut problem in an embedded undirected planar graph. Let p be the minimum number of faces that a curve from s to $t$ passes through. If p=1, that is, the vertices s and t are on the boundary of the same face, then the minimum cut can be found in O(n)time. For general planar graphs this cut can be found in O(n log n) time. We unify these results and give an O(n log p) time algorithm. We use cut-cycles to obtain the value of the minimum cut, and study the structure of these cycles to get an efficient algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haim Kaplan and Yahav Nussbaum 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.117 urn:nbn:de:0030-drops-30049 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.117 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode