python - 用于精确（加权）最大独立集的 Python 库

Question

我试图获得最大独立集问题的一些近似比，所以我需要一些精确的解决方案！

我找到了用 C++ 编写的库（即https://github.com/iPapatsoris/Maximum-Independent-Set），但想知道是否有任何直接在 Python 中。我知道“networkx”最大独立集函数，但这些只是近似值。

我意识到它远非最有效的语言，但我只解决小的 Erdős–Rényi 图（N<20）。

除此之外，是否有任何库可以解决加权问题，其中某些节点比其他节点更重要？

标签： pythonalgorithmgraph

Answer 1

这是我能找到的唯一 python 库：

https://github.com/pchervi/Graph-Coloring/blob/master/Coloring_MWIS_heuristics.py

但是，我还没有检查它是否正常工作。

我一直在使用 KaMIS，它是一个 C++ 实现。

https://github.com/KarlsruheMIS/KaMIS