Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs

Simple item page
dc.creatorDatta, Samir
dc.creatorKulkarni, Raghav
dc.creatorRoy, Sambuddha
dc.date2008-02-20
dc.date.accessioned2026-07-07T09:22:02Z
dc.date.available2026-07-07T09:22:02Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/0802.2850
dc.identifierhttp://arxiv.org/abs/0802.2850
dc.identifierDans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (2008)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155237
dc.subjectData Structures and Algorithms
dc.subjectCombinatorics
dc.titleDeterministically Isolating a Perfect Matching in Bipartite Planar Graphs
dc.typetext

Files

Collections

arXiv