論文

査読有り
2016年

An improved algorithm for parameterized edge dominating set problem

Journal of Graph Algorithms and Applications
  • Ken Iwaide
  • ,
  • Hiroshi Nagamochi

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.

リンク情報
DOI
https://doi.org/10.7155/jgaa.00383
DBLP
https://dblp.uni-trier.de/rec/journals/jgaa/IwaideN16
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=201702209568797060
URL
http://dblp.uni-trier.de/db/journals/jgaa/jgaa20.html#journals/jgaa/IwaideN16
ID情報
  • DOI : 10.7155/jgaa.00383
  • ISSN : 1526-1719
  • DBLP ID : journals/jgaa/IwaideN16
  • J-Global ID : 201702209568797060
  • SCOPUS ID : 84959549177

エクスポート
BibTeX RIS