Greedy algorithm for max matching / min vertex cover on tree

Revision en2, by lantrungseo, 2019-09-29 18:59:56

I don't know whether this idea has been discussed somewhere before, but I find it quite interesting.

PT07X — SPOJ

Summary of the problem: Given a tree find a largest set of edges such that no two edges share an endpoint (maximum matching), or to find minimal set of nodes such that each node outside the set must be adjacent to at least one node in the set (minimum vertex cover).

Usual algorithm: Dynamic programming (refer to this blog : Codeforces blog)

My (maybe-wrong) greedy idea:

  1. Root the tree at arbitrary node, let say node 1.

  2. Find the distances of other nodes to node 1 (means find the height of each node). Sort the nodes according to their distances to node 1 (means sort by height).

  3. Go from the node with greatest height, if this node is not used and its parent is not used, then we match this node with its parent.

My correct submission to above SPOJ problem: https://ideone.com/CeWhlr

Could anyone prove or disprove it? Thanks in advanced!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English lantrungseo 2019-09-29 18:59:56 103
en1 English lantrungseo 2019-09-29 18:56:57 1077 Initial revision (published)