2010/09/07 by Serge Gaspers, Mathieu Liedloff, Gaspers, Serge +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2 #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1009.1381
openalex publication_date 2010/09/07 · openalex created_date 2022/09/01 · openalex updated_date 2026/07/28
An independent dominating set D of a graph G = (V,E) is a subset of vertices\nsuch that every vertex in V D has at least one neighbor in D and D is an\nindependent set, i.e. no two vertices of D are adjacent in G. Finding a minimum\nindependent dominating set in a graph is an NP-hard problem. Whereas it is hard\nto cope with this problem using parameterized and approximation algorithms,\nthere is a simple exact O(1.4423n)-time algorithm solving the problem by\nenumerating all maximal independent sets. In this paper we improve the latter\nresult, providing the first non trivial algorithm computing a minimum\nindependent dominating set of a graph in time O(1.3569n). Furthermore, we give\na lower bound of \Ω(1.3247n) on the worst-case running time of this\nalgorithm, showing that the running time analysis is almost tight.\n