An Exact Algorithm for Lowest Edge Dominating Set
An Exact Algorithm for Lowest Edge Dominating Set
复制标题
DOI：
10.1587/transinf.2016fcp0005
复制
发表时间：
2017-03
期刊：
影响因子：
--
通讯作者：
Ken Iwaide;H. Nagamochi
中科院分区：
文献类型：
--
作者：
Ken Iwaide;H. Nagamochi
给定无向图 G，边支配集是边的子集 F，使得不在 F 中的每条边与 F 中的某些边相邻，并且计算边支配集的最小大小已知是 NP 困难的。由于任何边缘支配集的大小至少是 G 中匹配的最大大小 μ(G) 的一半，因此我们研究测试给定图 G 是否具有大小为 μ(G)/2 的边缘支配集的问题。在本文中，我们证明该问题是 NP 完全问题，同时我们为该问题设计了 O*(2.0801μ(G)/2) 时间和多项式空间算法。关键词: 图论, 边支配集, 算法, NP完备性, 固定参数易处理
Given an undirected graph G, an edge dominating set is a subset F of edges such that each edge not in F is adjacent to some edge in F, and computing the minimum size of an edge dominating set is known to be NP-hard. Since the size of any edge dominating set is at least half of the maximum size μ(G) of a matching in G, we study the problem of testing whether a given graph G has an edge dominating set of size μ(G)/2 or not. In this paper, we prove that the problem is NP-complete, whereas we design an O∗(2.0801μ(G)/2)-time and polynomial-space algorithm to the problem. key words: graph theory, edge dominating set, algorithm, NPcompleteness, fixed parameter tractable