CODEWITHSUNDEEP
graph-theorygraph-algorithm
StevieG
StevieG

Reputation: 309

Graph vertex cover - same degree vertex confusion

In order to solve the graph vertex cover problem, I started with selecting the vertex v having the maximum degree and then deleting that vertex from the set of vertices and also deleting the edges having end point as v. I had a question that what if after deleting the above vertices and edges, I have more than one vertex that has the same degree, which vertex will my greedy algorithm choose?

I tried searching online but could not find any suggestions for the above problem. If anybody can please help. Thanks

Upvotes: 0

Views: 152

Answers (1)

Christian
Christian

Reputation: 729

Ties can be broken arbitrarily. For example, you could choose randomly. If you need the algorithm to be deterministic you could, say, always pick the first vertex you come across in your data structure where your vertices are stored.

Upvotes: 1

Related Questions