Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MAXIMUM MATCHINGS:
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

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 >>>