Seminar by Raghunath Tewari
Green's Theorem and its application to the isolation problem in planar graphs
Raghunath Tewari
University of Nebraska-Lincoln, USA
Date: Monday, November 25th, 2010
Time: 11:15 AM
Venue: CS101.Abstract:
Green's Theorem is one of the most celebrated results in multi-variable calculus with a wide spectrum of applications extending to areas beyond mathematics. In this talk, we give an application of Green's Theorem to a problem in combinatorics, namely the isolation problem. In particular we show that isolating (a) minimum weight paths in directed planar graphs and (b) minimum weight perfect matchings in undirected bipartite planar graphs, can be done efficiently.