Fast Algorithms for min independent dominating set
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010), Fast Algorithms for min independent dominating set, in Patt-Shamir, Boaz; Ekim, Tinaz, Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings., Springer : Berlin, p. 247-261
TypeCommunication / Conférence
Conference titleSIROCCO 2010: 17th International Colloquium on Structural Information and Communication Complexity
Book titleStructural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.
Book authorPatt-Shamir, Boaz; Ekim, Tinaz
Series titleLecture Notes in Computer Science
MetadataShow full item record
Abstract (EN)We first devise a branching algorithm that computes a minimum independent dominating set with running time O *(20.424n ) and polynomial space. This improves the O *(20.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.
Subjects / Keywordsmin independent dominating set
Showing items related by title and author.
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié