License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.117
URN: urn:nbn:de:0030-drops-30049
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3004/
Go to the corresponding LIPIcs Volume Portal


Kaplan, Haim ; Nussbaum, Yahav

Minimum s-t cut in undirected planar graphs when the source and the sink are close

pdf-format:
14.pdf (0.7 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{kaplan_et_al:LIPIcs:2011:3004,
  author =	{Haim Kaplan and Yahav Nussbaum},
  title =	{{Minimum s-t cut in undirected planar graphs when the source and the sink are close}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{117--128},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3004},
  URN =		{urn:nbn:de:0030-drops-30049},
  doi =		{10.4230/LIPIcs.STACS.2011.117},
  annote =	{Keywords: planar graph, minimum cut, shortest path, cut cycle}
}

Keywords: planar graph, minimum cut, shortest path, cut cycle
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI