Green's Theorem and Isolation
in Planar Graphs
Meeting Time: Apr. 37, 2009, 2:00-2:50pm
Abstract:
We consider the following computational tasks.
(1) Given a directed graph G. Design a weight function for the edges so
that between every pair of vertices u and v, among all u-to-v hs in G,
the minimum weight u-to-v path is unique.
(2) Given an undirected bipartite graph G. Design a weight function the
edges so that among all the perfect matchings of G, the mimum weight
perfect matching is unique.
Designing such "isolating" weight functions that are space-efficiently
computable and polynomially bounded will imply major results in
complexity theory and is an outstanding open problem.
In this talk we show a simple application of a theorem due to 19th
century British mathematician and physicist George Green to the
above-mentioned isolation problems for the special case of planar graphs.
This is a joint work with Raghunath Tewari.