2016年
An improved algorithm for parameterized edge dominating set problem
Journal of Graph Algorithms and Applications
- ,
- 巻
- 20
- 号
- 1
- 開始ページ
- 23
- 終了ページ
- 58
- 記述言語
- 英語
- 掲載種別
- 研究論文(学術雑誌)
- DOI
- 10.7155/jgaa.00383
- 出版者・発行元
- Brown University
An edge dominating set of a graph G = (V,E) is a subset M ⊆ E of edges such that each edge in E\\M is incident to at least one edge in M. In this paper, we consider the parameterized edge dominating set problem which asks us to test whether a given graph has an edge dominating set with size bounded from above by an integer k or not, and we design an O*(2.2351k)-time and polynomial-space algorithm. This is an improvement over the previous best time bound of O*(2.3147k). We also show two corollaries: the parameterized weighted edge dominating set problem can be solved in O*(2.2351k) time and polynomial space
and a minimum edge dominating set of a graph G can be found in O*(1.7957τ) time where τ is the size of a minimum vertex cover of G.
and a minimum edge dominating set of a graph G can be found in O*(1.7957τ) time where τ is the size of a minimum vertex cover of G.
- リンク情報
- ID情報
-
- DOI : 10.7155/jgaa.00383
- ISSN : 1526-1719
- DBLP ID : journals/jgaa/IwaideN16
- J-Global ID : 201702209568797060
- SCOPUS ID : 84959549177