文章/答案/技术大牛

发布

社区首页 >问答首页 >包含给定节点集的最小连通子图

问包含给定节点集的最小连通子图
EN

Stack Overflow用户

提问于 2010-10-20 15:52:15

回答 1查看 8.5K关注 0票数 22

我有一个未加权的连通图。我想找到一个连通子图，它肯定包含一定的节点集，并且尽可能少的额外节点。如何做到这一点呢？

为了以防万一，我将用更精确的语言重申这个问题。设G(V，E)是无权无向连通图。设N是V的某个子集，求G(V，E)的最小连通子图G'( V‘，E')使得N是V’的子集的最佳方法是什么？

近似值很好。

发布于 2010-10-20 21:00:49

这就是众所周知的NP-hard Steiner Tree问题。如果没有更多关于实例外观的详细信息，就很难给出适当算法的建议。

票数 11

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/3975763

复制

相似问题

问包含给定节点集的最小连通子图EN