Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBourgeois, Nicolas*
hal.structure.identifier
dc.contributor.authorDella Croce, Federico*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2013-09-12T09:55:33Z
dc.date.available2013-09-12T09:55:33Z
dc.date.issued2012
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11641
dc.language.isoenen
dc.subjectDominating clique
dc.subjectExponential time algorithms
dc.subjectExact and approximation algorithms
dc.subject.ddc003en
dc.titleAlgorithms for dominating clique problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol459
dc.relation.isversionofjnlissue9
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages77-88
dc.relation.isversionofdoi10.1016/j.tcs.2012.07.016
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-01-23T09:42:33Z
hal.identifierhal-01509536*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record