Mittagsseminar (in cooperation with J. Lengler, A. Steger, and D. Steurer)

Date and Time: Thursday, September 20, 2012, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Christian Sommer (MIT)

Simple Cycle Separators and Recursive Decompositions for Planar Graphs

In the first part, we review the basics of planar separators (Lipton-Tarjan) and cycle separators (Miller).

In the second part, I shall give a brief outline of a recent result on recursive separator decompositions (also called r-divisions), obtained in collaboration with Philip N. Klein and Shay Mozes. For a preprint, see: http://www.sommer.jp/rdiv.htm

Given a planar graph G on n vertices and an integer parameter r, an r-division of G with few holes is a decomposition of G into O(n/r) regions of size at most r such that each region contains at most a constant number of faces that are not faces of G (also called holes), and such that, for each region, the total number of vertices on these faces is O(sqrt r).

We provide a linear-time algorithm for computing r-divisions with few holes. In fact, our algorithm computes a structure, called decomposition tree, which represents a recursive decomposition of G that includes r-divisions for essentially all values of r. In particular, given an exponentially increasing sequence r = (r_1,r_2,...), our algorithm can produce a recursive r-division with few holes in linear time.

r-divisions with few holes have been used in efficient algorithms to compute shortest paths, minimum cuts, and maximum flows. Our linear-time algorithm improves upon the decomposition algorithm used in the state-of-the-art algorithm for minimum st-cut (Italiano, Nussbaum, Sankowski, and Wulff-Nilsen, STOC 2011), removing one of the bottlenecks in the overall running time of their algorithm (analogously for minimum cut in planar and bounded-genus graphs).

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login