Explore BrainMass

Maximum cardinality matching algorithm

This content was STOLEN from BrainMass.com - View the original, and get the already-completed solution here!

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

© BrainMass Inc. brainmass.com October 24, 2018, 7:44 pm ad1c9bdddf

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.

See Also This Related BrainMass Solution

Flow Augmenting Path Algorithm, Bipartite Graph and Cardinality

1. Find the maximum flow and the associated minimum capacity cut for the following network, by using flow augmenting path algorithm (in the order of "first labeled, first scannred"). *see attachment for diagram*

2. A maximum capacity flow augmenting path is an augmenting path such that we can increase the flow of the network by the largest amount along this path comparing to all other augmenting paths. Design a strategy (similar to the strategy of finding a shortest path) to find a maximum capacity flow augmenting path. Use your strategy to find a maximum capacity flow augmenting path for the above network with the initial 0 flow.

3. Let G={X,E,Y} be the bipartite graph as follows *see attachment*
Using flow augmenting path algorithm find a maximum cardinality matching of the above G.

View Full Posting Details