Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-005 (February 08, 2011)

Parameterized Edge Dominating Set in Cubic Graphs
by Mingyu Xiao, Hiroshi Nagamochi

pdf File


In this paper, we present an improved algorithm to decide whether a graph of maximum degree $3$ has an edge dominating set of size $k$ or not, which is based on enumerating vertex covers. We first enumerate vertex covers of size at most $2k$ and then construct an edge dominating set based on each vertex cover to find a satisfied edge dominating set. To enumerate vertex covers, we use a branch-and-reduce method, which will generate a search tree of size $O(2.1479^k)$. Then we get the running time bound of the algorithm.