Fast algorithms for min independent dominating set
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2013), Fast algorithms for min independent dominating set, Seventh International Conference on Graphs and Optimization 2010, 2010-06, Ovronnaz, Switzerland
Type
Communication / ConférenceExternal document link
https://arxiv.org/abs/0905.1993v1Date
2013Conference title
Seventh International Conference on Graphs and Optimization 2010Conference date
2010-06Conference city
OvronnazConference country
SwitzerlandJournal name
Discrete Applied MathematicsVolume
161Number
4-5Publisher
Elsevier
Pages
558-572
558-572
Publication identifier
Metadata
Show full item recordAuthor(s)
Bourgeois, NicolasLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Della Croce, Federico
Escoffier, Bruno
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
We first devise a branching algorithm that computes a minimum independent dominating set with running time O∗(1.3351n)=O∗(20.417n)O∗(1.3351n)=O∗(20.417n) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1+ϵ1+ϵ, for any ϵ>0ϵ>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 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se.Subjects / Keywords
Approximation algorithms; min independent dominating set; Exact algorithms; Exponential algorithmsRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2009) 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é