2015 | OriginalPaper | Buchkapitel
An Improved Algorithm for Parameterized Edge Dominating Set Problem
Autoren: Ken Iwaide, Hiroshi Nagamochi
Verlag: Springer International Publishing
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 polynomial-space algorithm. This is an improvement over the previous best time bound of
O
*
(2.3147
k
). We also show that a related problem: the parameterized weighted edge dominating set problem can be solved in
O
*
(2.2351
k
) time and polynomial space.
