Minimal Dominating Set Enumeration
Minimal Dominating Set Enumeration
复制标题
最小支配集枚举
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Lhouari Nourine
中科院分区：
文献类型：
--
作者：
M. Kanté;Lhouari Nourine
设G是一个有n个顶点和m条边的图。一条边写为xy（等于yx）。G中的支配集是顶点D的集合，使得G的每个顶点要么在D中，要么与D的某个顶点相邻。如果它不包含任何其他支配集作为固有子集，则称为最小。对于每个顶点x，令N [x]为{x}∪{y | xy∈E}，且对于每个S∈V，令N [S]:=∈x∈sn [x]。对于S∈V， x∈S，我们称任意y∈N [x] N [S x]是x关于S的一个私有邻域。G的最小支配集记为D(G)。我们感兴趣的是一种用于枚举D(G)的输出多项式算法，即列出D(G)的所有元素，不重复，在以p(n+m)∑为界的时间内
Let G be a graph on n vertices and m edges. An edge is written xy (equivalently yx). A dominating set in G is a set of vertices D such that every vertex of G is either in D or is adjacent to some vertex of D. It is said to be minimal if it does not contain any other dominating set as a proper subset. For every vertex x let N [x] be {x} ∪ {y | xy ∈ E}, and for every S ⊆ V let N [S] := ⋃ x∈S N [x]. For S ⊆ V and x ∈ S we call any y ∈ N [x] N [S x] a private neighbor of x with respect to S. The set of minimal dominating sets of G is denoted by D(G). We are interested in an output-polynomial algorithm for enumerating D(G), i.e., listing, without repetitions, all the elements of D(G) in time bounded by p(n+m, ∑