A refined exact algorithm for Edge Dominating Set

In this paper, we present a new exact algorithm for the Edge Dominating Set problem, and analyze its running time by the Measure and Conquer method. Our algorithm runs in 1.3160nnO(1)1.3160nnO(1) time for a graph with n vertices, which is the currently fastest known time for the Edge Dominating Set problem. By designing new branching rules based upon conceptually simple local structures, which we call clique-producing vertices and cycles, we obtain an algorithm that is simpler than the previously fastest known algorithm and has an improved time bound as well.