Let $T(V,E)$ be a tree. Design linear time (i.e., $O(|V|)$ time) algorithms for the following problems :
Find an optimal vertex cover in $T$.
Find a maximum matching in $T$.
Find a maximum independent set in $T$.
Posted: Jun 08 '12
Seen: 61 times
Last updated: Jun 09 '12