CODEWITHSUNDEEP
algorithmtime-complexitygraph-theory
DavieRodger
DavieRodger

Reputation: 31

Vertex Cover of a Tree Linear or Polynomial Time?

I have the following algorithm to find the minimum vertex cover of a tree. That is a minimal sized set S of vertices such that for every edge (v,u) in G either v is in S or u is in S.

I have been told the algorithm has linear time complexity, however I don't understand how this is the case, since isn't the number of edges incident to u of the order O(n) and so the complexity would be O(n^2)?

Let T = <V, E> be a Tree. That is, the vertex set is V, the edge set is E. Also suppose the cover set = C. The algorithm can be described as follows:

while V != [] do
    Identify a leaf vertex v
    Locate u = parent(v), the parent vertex of v.
    Add u to C
    Remove all the edges incident to u
return C.

Upvotes: 2

Views: 707

Answers (1)

Dave
Dave

Reputation: 9085

In a tree, |E| = |V| - 1, so there are O(n) edges to deal with in total.

Upvotes: 1

Related Questions