Home  Issues  Aims and Scope  Instructions for Authors 
Special Issue on Selected Papers from the Ninth International Workshop on Algorithms and Computation (WALCOM 2015)
DOI: 10.7155/jgaa.00383
An Improved Algorithm for Parameterized Edge Dominating Set Problem
Ken Iwaide and
Hiroshi Nagamochi
Vol. 20, no. 1, pp. 2358, 2016. Regular paper.
Abstract 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.2351^{k})time and polynomialspace algorithm. This is an improvement over the previous best time bound of O^{*}(2.3147^{k}). We also show two corollaries: the parameterized weighted edge dominating set problem can be solved in O^{*}(2.2351^{k}) 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.

Submitted: March 2015.
Reviewed: July 2015.
Revised: November 2015.
Accepted: November 2015.
Final: January 2016.
Published: February 2016.
