CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
Rafael Rios
Rafael Rios

Reputation: 583

How to find a minimal set of routes to visit all nodes in a graph from a given set of routes?

From a given graph, not necessarily connected, and a set of paths, where each path visit a set of nodes in the graph. And the nodes visited by two different paths may or may not be exclusive.

With that information is there a way to find the minimun number of paths needed to visit all the nodes in the graph? Is there some well defined problem in graph theory, like the travel salesman, that covers this problem?, if there is would you please be so kind to tell me which is its name so i can look for an answer.

Thanks

Upvotes: 0

Views: 813

Answers (1)

Boris Strandjev
Boris Strandjev

Reputation: 46943

This is equivalent to minimum set cover and is known to be NP-complete problem. See here.

Consider every path of those you are interested in as a subset of the set of all graph vertices and you get the same problem.

Upvotes: 3

Related Questions