Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with K5-free:
TR14-161 | 27th November 2014
Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari

Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs

Revisions: 2

The perfect matching problem has a randomized $NC$ algorithm, using the celebrated Isolation Lemma of Mulmuley, Vazirani and Vazirani. The Isolation Lemma states that giving a random weight assignment to the edges of a graph, ensures that it has a unique minimum weight perfect matching, with a good probability. We ... more >>>

ISSN 1433-8092 | Imprint