Exponential Time Algorithms for the Minimum Dominating Set Problem on Some Graph Classes

摘要

The Minimum Dominating Set problem remains NP-hard when restricted to chordal graphs, circle graphs and c-dense graphs (i.e. ∣E∣ ≥ cn~2 for a constant c, 0 < c < 1/2). For each of these three graph classes we present an exponential time algorithm solving the Minimum Dominating Set problem. The running times of those algorithms are O(1.4173~n) for chordal graphs, 0(1.4956~n) for circle graphs, and O(1.2303~((1+(1-2c)~(1/2))n)) for c-dense graphs.