2015 | OriginalPaper | Buchkapitel
An Improved Algorithm for Parameterized Edge Dominating Set Problem
verfasst von : Ken Iwaide, Hiroshi Nagamochi
Erschienen in: WALCOM: Algorithms and Computation
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.