
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
View/ Open
Type
Communication / ConférenceDate
2010Conference title
SIROCCO 2010: 17th International Colloquium on Structural Information and Communication ComplexityConference date
2010-06Conference city
SirinceConference country
TurquieBook title
Structural Information and Communication Complexity, 17th International Colloquium, SIROCCO 2010, Sirince, Turkey, June 7-11, 2010. Proceedings.Book author
Patt-Shamir, Boaz; Ekim, TinazPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
6058Published in
Berlin
ISBN
978-3-642-13283-4
Pages
247-261
Publication identifier
Metadata
Show full item recordAbstract (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 / Keywords
min independent dominating setRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis; Van Rooij, Johan (2012) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2008) Communication / Conférence