CODEWITHSUNDEEP
algorithmgraphgraph-algorithmminimum-spanning-treedirected-graph
skanatek
skanatek

Reputation: 5251

Minimum spanning tree in a graph with multiple root vertices

I would like to know if there is an algorithm which computes a minimum spanning tree (optimum branching) in a directed graph given a set of root vertices between all of these root vertices, but not only one root vertex and all other vertices in a graph.

Given a set of root vertices [1,4,6] and a graph G like the one on the following picture:

enter image description here

...the algorighm should return something like a green sub-graph on the same picture.

I would like to get such an MST that connects all the root vertices provided to the algorithm. I tend to think that the result of the would-be algorithm is a sub-graph of the graph G which contains all root vertices and some other vertices from G.

Notes:

  1. I know that there is no MST for a directed graph, but there is Chu–Liu/Edmonds algorithm.
  2. I guess that a result of such an algorithm (if it is actually possible) will return an optimum branching, which includes some vertices of a graph along with all root vertices.

Upvotes: 1

Views: 2058

Answers (1)

hugomg
hugomg

Reputation: 69924

Minimum Spanning Trees are supposed to span all the vertices. I think you might be actually dealing with a Steiner Tree problem, given that you only need to connect a subset of them. Unfortunately, the traditional Steiner tree problem with undirected edges is already NP complete so you have a tough road ahead of you.

Upvotes: 2

Related Questions