Archivio Istituzionale della RicercaWe 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.
Exact algorithms for dominating clique problems / N., Bourgeois; DELLA CROCE DI DOJOLA, Federico; B., Escoffier; V. T., Paschos. - 5878:(2009), pp. 4-13. (Intervento presentato al convegno 20th International Symposium, ISAAC 2009 tenutosi a Honolulu, Hawaii (USA) nel December 16-18, 2009) [10.1007/978-3-642-10631-6_3].
Exact algorithms for dominating clique problems
DELLA CROCE DI DOJOLA, Federico;
2009
Abstract
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.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2302842
Attenzione
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo