Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2011-014 (September 22, 2011)
A Refined Exact Algorithm for Edge Dominating Set
by Mingyu Xiao and Hiroshi Nagamochi
We present an $O^*(1.3160^n)$-time algorithm for the edge dominating set problem in an $n$-vertex graph, which improves previous exact algorithms for this problem.
The algorithm is analyzed by using the ``Measure and Conquer method."
We design new branching rules based on conceptually simple local structures,
called ``clique-producing vertices/cycles,"
which significantly simplify the algorithm and its running time analysis,
attaining an improved time bound at the same time.