Editing Matching (graph theory) (section)

=== Finding all maximally matchable edges ===
{{Main|Maximally matchable edge}}
One of the basic problems in matching theory is to find in a given graph all edges that may be extended to a maximum matching in the graph (such edges are called [[maximally matchable edge]]s, or '''allowed''' edges). Algorithms for this problem include:

* For general graphs, a deterministic algorithm in time <math>O(VE)</math> and a randomized algorithm in time <math>\tilde{O}(V^{2.376}) </math>.<ref>{{citation
| last1 = Rabin | first1 = Michael O.
| last2 = Vazirani | first2 = Vijay V.
| title = Maximum matchings in general graphs through randomization
| journal = [[Journal of Algorithms]]
| volume = 10
| year = 1989
| issue = 4
| pages = 557–567
|  doi = 10.1016/0196-6774(89)90005-9| citeseerx = 10.1.1.228.1996
}}</ref><ref>
{{citation
| last1 = Cheriyan | first1 = Joseph
| title = Randomized <math>\widetilde O(M(|V|))</math> algorithms for problems in matching theory
| journal = [[SIAM Journal on Computing]]
| volume = 26
| year = 1997
| number = 6
| pages = 1635–1655
| doi = 10.1137/S0097539793256223
}}</ref>
* For bipartite graphs, if a single maximum matching is found, a deterministic algorithm runs in time <math>O(V+E)</math>.<ref>{{citation
| last1 = Tassa | first1= Tamir
| title = Finding all maximally-matchable edges in a bipartite graph
| journal = [[Theoretical Computer Science]]
| volume = 423
| year = 2012
| pages = 50–58
| doi = 10.1016/j.tcs.2011.12.071
| doi-access = free
}}</ref>