Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Samir Datta, Raghav Kulkarni & Sambuddha Roy
We present a deterministic way of assigning small (log bit) weights to the edges of a bipartite planar graph so that the minimum weight perfect matching becomes unique. The isolation lemma as described in (Mulmuley et al. 1987) achieves the same for general graphs using a randomized weighting scheme, whereas we can do it deterministically when restricted to bipartite planar graphs. As a consequence, we reduce both decision and construction versions of the matching problem...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our Documentation.