Algorithms for dominating clique problems

详细信息    查看全文

• 作者：N. Bourgeois ; F. Della Croce ; B. Escoffier ; V.Th. Paschos
• 关键词：Dominating clique ; Exponential time algorithms ; Exact and approximation algorithms
• 刊名：Theoretical Computer Science
• 出版年：2012
• 出版时间：9 November, 2012
• 年：2012
• 卷：459
• 期：Complete
• 页码：77-88
• 全文大小：289 K

文摘

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?, if? 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.