I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.
Find a maximum matching in linear time
algorithms;graphs;matching