Technion
 
The Operations Research & Statistics seminar
 
Date: April 29, 2013
 
____________________________________________________________________________
 
Speaker: Yahav Nussbaum from TAU
 
Title: Maximum Flow in Planar Graphs
 
Time and place: 12:30 in Bloomfield-527
 
Abstract:
A graph is planar if it can be embedded in the plane such that no two edges
intersect. Planar graphs appear in many applications, such as road transportation,
VLSI design, computer vision, and others. The rich combinatorial
structure of planar graphs allows us to find efficient algorithms for classical
combinatorial problems in this kind of graphs, that have better time bounds
than algorithms for general graphs.
In this talk I will describe planarity-exploiting algorithms for some versions
of the maximum flow problem in planar graphs. Our results are based on
two main tools. The first is the associated dual graph, which exists for every
planar graph. The second is a divide-and-conquer approach based on planar
graphs separators.
The talk is based on a joint work with Glencora Borradaile, Philip N. Klein,
Jakub Lacki, Shay Mozes, Piotr Sankowski and Christian Wulff-Nilsen
 
____________________________________________________________________________
 
You can watch the rest of the seminar plan at our web site
 
____________________________________________________________________________
Or-seminar mailing list
 <Or-seminar@iemm1.technion.ac.il>
 <http://iemm1.technion.ac.il/mailman/listinfo/or-seminar>
_______________________________________________
Statseminar mailing list
 <Statseminar@iemm1.technion.ac.il>
 <http://iemm1.technion.ac.il/mailman/listinfo/statseminar>
 
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from:  <tomerk@.technion.ac.il>