Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with maximum matchings:
TR04-076 | 17th September 2004
Oliver Giel, Ingo Wegener

Searching Randomly for Maximum Matchings

Many real-world optimization problems in, e.g., engineering
or biology have the property that not much is known about
the function to be optimized. This excludes the application
of problem-specific algorithms. Simple randomized search
heuristics are then used with surprisingly good results. In
order to understand the working principles behind such
more >>>

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