开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >寻找完美图的所有独立集

问寻找完美图的所有独立集
EN

Stack Overflow用户

提问于 2017-07-25 15:32:32

回答 1查看 259关注 0票数 0

我读到完美图的最大独立集可以在多项式时间内找到。

有没有什么多项式时间算法可以找到一个完美图的所有独立集的列表？

independent-set

EN

回答 1

Stack Overflow用户

发布于 2017-07-25 19:09:14

在完全图(graph classes)中，可以在多项式时间内找到最大独立集。至于列出n个节点的完美图的所有独立集:在我看来，所有独立集的数量似乎是指数级的。但是，由于Wikipedia，可以使用软件列出所有的极大独立集。

票数 0

EN

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

原文链接：

https://stackoverflow.com/questions/45296720

复制

相似问题