Back
maximal-matching (clj)
(source)function
(maximal-matching g)
Find a maximal matching in the graph.
A matching is a subset of edges in which no node occurs more than once.
A maximal matching cannot add more edges and still be a matching.
Parameters
----------
`g` : Undirected graph
Returns
-------
matching : set
A maximal matching of the graph.
Notes
-----
The algorithm greedily selects a maximal matching M of the graph G
(i.e. no superset of M exists). It runs in $O(|E|)$ time.