Complexity of Domination-Type Problems in Graphs
Complexity of Domination-Type Problems in Graphs
复制标题
DOI：
--
复制
发表时间：
1994-03
期刊：
影响因子：
--
通讯作者：
J. A. Telle
中科院分区：
文献类型：
--
作者：
J. A. Telle
许多图参数是目标函数在选定的顶点子集S上的最优值，其中对S中的顶点和不在S中的顶点可以具有多少选定的邻居顶点有一些约束。经典的例子是最小控制集和最大独立集。我们给出了这些图形参数的一个特征，统一了它们的定义，方便了它们的常见算法处理，并允许它们的统一复杂性分类。这一特征为支配型和独立型问题的分类提供了基础。我们调查的计算复杂性的问题，在这个分类，确定类NP完全问题和类的问题在多项式时间内解决。
Many graph parameters are the optimal value of an objective function over selected subsets S of vertices with some constraint on how many selected neighbors vertices in S, and vertices not in S, can have. Classic examples are minimum dominating set and maximum independent set. We give a characterization of these graph parameters that unifies their definitions, facilitates their common algorithmic treatment and allows for their uniform complexity classification. This characterization provides the basis for a taxonomy of domination-type and independence-type problems. We investigate the computational complexity of problems within this taxonomy, identify classes of NP-complete problems and classes of problems solvable in polynomial time.