graph - 找到完美图的所有独立集

Question

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

是否有任何多项式时间算法可以找到完美图的所有独立集的列表？

Answer 1

确实，最大独立集可以在完美图（图类）的多项式时间内找到。至于具有 n 个节点的完美图的所有独立集的列表：在我看来，所有独立集的数量都是指数的。但是列出所有最大独立集软件是可用的，因为Wikipedia。