Exact Algorithms for Dominating Clique Problems

Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis

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

cahierLamsade285.pdf (376.4Kb)

Type

Communication / Conférence

Date

2009

Conference title

ISAAC 2009 20th International Symposium on Algorithms and Computation

Conference date

2009-12

Conference city

Hawaï

Conference country

États-Unis

Book title

Algorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings

Book author

Ibarra, Oscar H.; Du, Ding-Zhu; Dong, Ying Fei

Publisher

Springer

Series title

Lecture Notes in Computer Science

Series number

5878

Published in

Berlin

ISBN

978-3-642-10630-9

Pages

4-13

Abstract (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 Algorithms