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

pdf File

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.