Exponential time algorithms for the minimum dominating set problem on some graph classes

• DOI: 10.1145/1644015.1644024
• Publication Date: 2010-08-24T13:16:40Z
• Authors: Serge Gaspers; Dieter Kratsch; Mathieu Liedloff; Ioan Todinca
• Keywords: Interval graph; Indifference graph; Split graph; Maximal independent set; Treewidth

The minimum dominating set problem remains NP-hard when restricted to any of the following graph classes: c -dense graphs, chordal 4-chordal weakly and circle graphs. Developing using a general approach, for each these classes we present an exponential time algorithm solving faster than best known Our algorithms have running time: O (1.4124 n ) (1.4776 (1.4845 (1.4887 (1.2273 (1+√1−2