I know about Steiner Tree Problem. It is stated as

Input to Steiner Tree Problem is a weighted graph G and a subset T of the nodes (called terminal nodes) and goal is to find a minimum weight tree that spans all the nodes in T.

Can we give a polynomial time algorithm to solve the Steiner Tree Problem such that |T| ≥ n−1 where n is the number of nodes in the original graph. I've done a lot of RnD on it but it is still confusing. Can any one help me out?

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top