An Improved Algorithm for Parameterized Edge Dominating Set Problem
Ken Iwaide and Hiroshi Nagamochi
Vol. 20, no. 1, pp. 23-58, 2016. Regular paper.
Abstract An edge dominating set of a graph G = (V, E) is a subset ME 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.
Submitted: March 2015.
Reviewed: July 2015.
Revised: November 2015.
Accepted: November 2015.
Final: January 2016.
Published: February 2016.
Communicated by M. Sohel Rahman and Etsuj Tomita
article (PDF)