Explore BrainMass

Maximum cardinality matching algorithm

A tree is a connected undirected graph with no cycles. Design a linear time algorithm to find a maximum cardinality matching in a tree.

Solution Preview

Please see the attached.

Algorithm Maximum (T)
Input: T is a rooted tree with n nodes.
Output: A maximum matching M
number the nodes of T by a BFS (Breadth First Search)
(check the nodes with the backward order of the numbers)
for every node do
if the node or its parent is marked then
skip this node
mark its parent
add the edge to M

The BFS costs time of O(n) and the loop also costs time of O(n), so the time
complexity of the above algorithm is O(n).

Suppose T is a tree with a root r(T). Number the nodes by a Breadth First Search (BFS) starting at r(T). Suppose the size of T is n. Number the nodes of T with numbers from 1 to n. The root is ...

Solution Summary

Maximum cardinality matching algorithm example is provided in the solution.