1 Search Results for "Nussbaum, Yahav"


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

Authors: Haim Kaplan and Yahav Nussbaum

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


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.

Cite as

Haim Kaplan and Yahav Nussbaum. Minimum s-t cut in undirected planar graphs when the source and the sink are close. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 117-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{kaplan_et_al:LIPIcs.STACS.2011.117,
  author =	{Kaplan, Haim and Nussbaum, Yahav},
  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 =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.117},
  URN =		{urn:nbn:de:0030-drops-30049},
  doi =		{10.4230/LIPIcs.STACS.2011.117},
  annote =	{Keywords: planar graph, minimum cut, shortest path, cut cycle}
}
  • Refine by Author
  • 1 Kaplan, Haim
  • 1 Nussbaum, Yahav

  • Refine by Classification

  • Refine by Keyword
  • 1 cut cycle
  • 1 minimum cut
  • 1 planar graph
  • 1 shortest path

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail