Show simple item record

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorDella Croce, Federico
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-04-12T13:41:40Z
dc.date.available2010-04-12T13:41:40Z
dc.date.issued2009
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3936
dc.language.isoenen
dc.subjectOptimal Algorithmsen
dc.subject.ddc003en
dc.titleExact Algorithms for Dominating Clique Problemsen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages4-13en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber5878
dc.relation.ispartoftitleAlgorithms and Computation 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings
dc.relation.ispartofeditorIbarra, Oscar H.
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofeditorDong, Ying Fei
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin
dc.relation.ispartofdate2009
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-10631-6
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/978-3-642-10631-6_3
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-10630-9
dc.relation.conftitleISAAC 2009 20th International Symposium on Algorithms and Computationen
dc.relation.confdate2009-12
dc.relation.confcityHawaïen
dc.relation.confcountryÉtats-Unisen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record