Thumbnail - Request a copy

Algorithms for dominating clique problems

Bourgeois, Nicolas; Della Croce, Federico; Escoffier, Bruno; Paschos, Vangelis (2012), Algorithms for dominating clique problems, Theoretical Computer Science, 459, 9, p. 77-88. 10.1016/j.tcs.2012.07.016

Type
Article accepté pour publication ou publié
Date
2012
Journal name
Theoretical Computer Science
Volume
459
Number
9
Publisher
Elsevier
Pages
77-88
Publication identifier
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas
Laboratoire 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 handle in this paper three dominating clique problems, namely, the decision problem to detect whether a graph has a dominating clique and two optimization versions asking to compute a maximum- and a minimum-size dominating clique of a graph G, if G has a dominating clique. For the three problems we propose exact moderately exponential algorithms with worst-case running time upper bounds improving those by Kratsch and Liedloff [D. Kratsch, M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoret. Comput. Sci. 385 (1–3) (2007) 226–240]. We then study the three problems in sparse and dense graphs also providing improved running time upper bounds. Finally, we propose some exponential time approximation algorithms for the optimization versions.
Subjects / Keywords
Dominating clique; Exponential time algorithms; Exact and approximation algorithms