
Exact Algorithms for Dominating Clique Problems
Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2009), Exact Algorithms for Dominating Clique Problems, in Ibarra, Oscar H.; Du, Ding-Zhu; Dong, Ying Fei, Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Springer : Berlin, p. 4-13
View/ Open
Type
Communication / ConférenceDate
2009Conference title
ISAAC 2009 20th International Symposium on Algorithms and ComputationConference date
2009-12Conference city
HawaïConference country
États-UnisBook title
Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. ProceedingsBook author
Ibarra, Oscar H.; Du, Ding-Zhu; Dong, Ying FeiPublisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
5878Published in
Berlin
ISBN
978-3-642-10630-9
Pages
4-13
Publication identifier
Metadata
Show full item recordAbstract (EN)
We handle in this paper three dominating clique problems, namely, the decision problem itself when one asks if there exists a dominating clique in a graph G and two optimization versions where one asks for a maximum- and a minimum-size dominating clique, if any. For the three problems we propose optimal algorithms with provably worst-case upper bounds improving existing ones by (D. Kratsch and M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoretical Computer Science 385(1-3), pp. 226–240, 2007). We then settle all the three problems in sparse and dense graphs also providing improved upper running time bounds.Subjects / Keywords
Optimal AlgorithmsRelated items
Showing items related by title and author.
-
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 (2013) Communication / Conférence
-
Della Croce, Federico; Escoffier, Bruno; Kaminski, Marcin; Paschos, Vangelis (2008) Chapitre d'ouvrage
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2010) Communication / Conférence