Suggest a Book

# Linear time algorithms on trees

Level: unknown

posted Jun 08 '12

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

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

Source: folklore
delete retag edit

## Stats

Posted: Jun 08 '12

Seen: 61 times

Last updated: Jun 09 '12