支配集算法

支配集算法（dominating set algorithm），理学-计算机科学技术-计算机科学理论-算法-组合算法，支配集算法是求解支配集问题的算法。支配集（Dominating Set，DS）是图论中的一个常用概念。在无向图中，支配集 指顶点集合的子集，使得图中所有不在D中的顶点至少有一个邻居在中。对于一个图，包含顶点最少的支配集称为最小支配集（Minimum Dominating Set，MDS）。求一个图的最小支配集是一个NP难问题。这是一个简单的无向图，其中和。对于图，支配集包括和。在所有支配集中，具有最少的顶点个数，因此也称为图的最小支配集。针对最小支配集问题的算法研究较少。