sandesh247/problems — Issue #3: Vertex cover in a tree
Author: sandesh247
Created: 2011-10-19 05:38:01+00:00
State: open
Labels: algorithm, dynamic programming, graph, n

A vertex cover of a graph G = (V, E) is a subset of vertices S ⊆ V that includes at least one endpoint of every edge in E. Give a linear-time algorithm to ﬁnd the smallest vertex cover of a given undirected tree T = (V, E).