Geodesic
An Improved Algorithm for Parameterized Edge Dominating Set Problem
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015) , Tome 20 (2016) no. 1, pp. 23-58.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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. 
@article{JGAA_2016_20_1_a2,
     author = {Ken Iwaide and Hiroshi Nagamochi},
     title = {An {Improved} {Algorithm} for {Parameterized} {Edge} {Dominating} {Set} {Problem}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {23--58},
     publisher = {mathdoc},
     volume = {20},
     number = {1},
     year = {2016},
     doi = {10.7155/jgaa.00383},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00383/}
}
TY  - JOUR
AU  - Ken Iwaide
AU  - Hiroshi Nagamochi
TI  - An Improved Algorithm for Parameterized Edge Dominating Set Problem
JO  - Journal of Graph Algorithms and Applications
PY  - 2016
SP  - 23
EP  - 58
VL  - 20
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00383/
DO  - 10.7155/jgaa.00383
LA  - en
ID  - JGAA_2016_20_1_a2
ER  - 
%0 Journal Article
%A Ken Iwaide
%A Hiroshi Nagamochi
%T An Improved Algorithm for Parameterized Edge Dominating Set Problem
%J Journal of Graph Algorithms and Applications
%D 2016
%P 23-58
%V 20
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00383/
%R 10.7155/jgaa.00383
%G en
%F JGAA_2016_20_1_a2
Ken Iwaide; Hiroshi Nagamochi. An Improved Algorithm for Parameterized Edge Dominating Set Problem. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation  (WALCOM 2015)
					, Tome 20 (2016) no. 1, pp. 23-58. doi : 10.7155/jgaa.00383. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00383/

Cité par Sources :