最小支配集 -- 来自 Wolfram MathWorld

最小支配集

最小支配集是给定图中最小尺寸的支配集。最小支配集的大小被称为图的支配数。

最小支配集总是极小支配集，但反之不一定成立。

找到一般图的最小支配集是 NP 完全问题，这可以通过从顶点覆盖问题的归约来证明 (Garey and Johnson 1983, Mertens 2024)。这意味着不存在多项式时间算法来计算最小支配集。已知最快的算法找到具有顶点数的通用图的最小支配集的时间复杂度为 (van Rooij and Bodlaender 2011, Mertens 2024)。

另请参阅

支配数, 支配多项式, 支配集, 极小支配集

使用 Wolfram|Alpha 探索

更多尝试

参考文献

Garey, M. R. 和 Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, 1983.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 2024 年 8 月 15 日. https://arxiv.org/abs/2408.08053.van Rooij, J. M. M. 和 Bodlaender, H. L. "Exact Algorithms for Dominating Set." Discr. Appl. Math. 159, 2147-2164, 2011.

请引用为

Weisstein, Eric W. "最小支配集。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/MinimumDominatingSet.html