Advertisement
Published in:
2010 | OriginalPaper | Chapter
Exact and Parameterized Algorithms for Edge Dominating Set in 3-Degree Graphs
Author : Mingyu Xiao
Published in: Combinatorial Optimization and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a graph
G
= (
V
,
E
), the
edge dominating set
problem is to find a minimum set
M
⊆
E
such that each edge in
E
–
M
has at least one common endpoint with an edge in
M
. The edge dominating set problem is an important graph problem and has been extensively studied. It is well known that the problem is NP-hard, even when the graph is restricted to a planar or bipartite graph with maximum degree 3. In this paper, we show that the edge dominating set problem in graphs with maximum degree 3 can be solved in
O
*
(1.2721
n
) time and polynomial space, where
n
is the number of vertices in the graph. We also show that there is an
O
*
(2.2306
k
)-time polynomial-space algorithm to decide whether a graph with maximum degree 3 has an edge dominating set of size
k
or not. Above two results improve previously known results on exact and parameterized algorithms for this problem.