Monday November 15 4:00 - 5:00 PM Kelley 1001
Christian Wulff-Nilsen Postdoctoral Fellow School of Computer Science Carleton University Min st-Cuts in Planar Graphs Given vertices s and t in a graph G = (V,E) with non-negative edge weights, an st-cut is a partition of V into subsets S and T = V\S such that s is in S and t is in T. The weight of the st-cut is the sum of weights of edges starting in S and ending in T. A min st-cut is an st-cut of minimum weight. Computing min st-cuts is a well-studied algorithmic problem and is of both theoretical and practical interest. In my talk, I will consider the problem for planar undirected graphs and show how to solve it in O(n log log n) time, where n is the size of the graph. The previous best time bound was O(n log n). Biography Christian Wulff-Nilsen is a postdoctoral fellow at the School of Computer Science, Carleton University. He received his PhD in computer science from the University of Copenhagen in June 2010. His current focus of research is on algorithms for planar graphs and, more generally, graphs with a fixed excluded minor. Originating from the viking region of Scandinavia, Christian has a tendency to go berserk. He enjoys the music of Jean Michel Jarre and Philip Glass and wants to be reborn in the Twin Peaks universe. _______________________________________________ Colloquium mailing list [email protected] https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
