Chennai Mathematical Institute

Seminars




Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
Raghav Kulkarni
University of Chicago, USA.
06-09-07


Abstract

We will present a method to assign the small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. It is know that such an isolation is possible using random assignment of weights in general graphs.

Our method gives a highly parallel SPL algorithm for finding a perfect matching in bipartite planar graphs.

The techniques are elementary and the talk will be accessible to everyone.

* This is a part of the joint work with Dr. Samir Datta while the speaker was visiting Chennai Mathematical Institute, India.