Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or the total amount of edge weight) included in the tree is minimum.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
This is the famous Steiner tree problem in graphs, which is known as NP-hard.
-
12$\begingroup$ Of course, there are still algorithms for NP-hard problems. $\endgroup$ Jul 9, 2018 at 11:24
-
7$\begingroup$ @DavidRicherby It does suggest that the OP would need to provide quite a lot more information in order to suggest which algorithm will meet their requirements. Often the key to an efficient algorithm on such a problem is to take advantage of structure in the data which let you sidestep the pathologically difficult cases. $\endgroup$ Jul 9, 2018 at 19:56
-
1$\begingroup$ @CortAmmon The question doesn't ask for an efficient algorithm: it asks for an algorithm. Even if no efficient algorithm is available for the asker's case, they still want an algorithm. $\endgroup$ Jul 9, 2018 at 23:24