We first devise a branching algorithm that computes a minimum independent dominating set with running time O~*(2~(0.424n)) and polynomial space. This improves the O~*(2~(0.441n)) result by (S. Gaspers and M. Liedloff. A branch-and-reduce algorithm for finding a minimum independent dominating set in graphs, Proc. WG'06). We then study approximation of the problem by moderately exponential algorithms and show that it can be approximated within ratio 1 + ε, for any ε > 0, in a time smaller than the one of exact computation and exponentially decreasing with ε. We also propose approximation algorithms with better running times for ratios greater than 3.
展开▼
