Linear time algorithms on trees

posted Jun 08 '12

Shiva Kintali
691 ● 1 ● 6 ● 21
http://www.cs.princeton.e...

updated Jun 09 '12

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$.