Computer Science – Data Structures and Algorithms
Scientific paper
2008-02-20
Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (
Computer Science
Data Structures and Algorithms
Scientific paper
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 to testing whether a matrix is singular, under the promise that its determinant is 0 or 1, thus obtaining a highly parallel SPL algorithm for bipartite planar graphs. This improves the earlier known bounds of non-uniform SPL by (Allender et al. 1999) and $NC^2$ by (Miller and Naor 1995, Mahajan and Varadarajan 2000). It also rekindles the hope of obtaining a deterministic parallel algorithm for constructing a perfect matching in non-bipartite planar graphs, which has been open for a long time. Our techniques are elementary and simple.
Datta Samir
Kulkarni Raghav
Roy Sambuddha
No associations
LandOfFree
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647822