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.

Examples