Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > GIBBS DISTRIBUTION:
Reports tagged with Gibbs Distribution:
TR11-099 | 11th July 2011
Anant Jindal, Gazal Kochar, Manjish Pal

Maximum Matchings via Glauber Dynamics

Revisions: 1 , Comments: 1

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs G = (V, E). This problem has been studied extensively more than four decades. The best known algorithm for this problem till date runs in O(m \sqrt{n}) time due to Micali and Vazirani ... more >>>




ISSN 1433-8092 | Imprint