דלג לתוכן (מקש קיצור 's')
אירועים

אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

event speaker icon
יהב נוסבאום (אונ' תל-אביב)
event date icon
יום רביעי, 02.03.2011, 12:30
event location icon
טאוב 701
The problem of finding the minimum s-t cut between a source s and a sink t in a graph is a well-studied problem in computer science. Finding the minimum s-t cut in a planar graph has applications in many fields - from traffic design to computer vision.

The geometrical duality between a minimum s-t cut in an undirected planar graph and cycle on the plane that separates t from s was first used by Itai and Shiloach to solve the minimum cut problem, and more efficient algorithms for the problem using the same approach followed.

We use this approach to show an algorithm that finds the minimum s-t cut in an n-vertices undirected planar graph in O(n log log n) time. We then use the improved minimum cut algorithm to solve related problems, including the maximum flow problem in undirected planar graphs, within the same time bound.

Using a similar technique we obtain a dynamic data structure that allows edge capacity changes and answers minimum cut queries between any pair of vertices in O(n^(2/3) polylog(n)) time for undirected planar graphs.

Joint work with Giuseppe F. Italiano, Piotr Sankowski, and Christian Wulff-Nilsen