Exponential time algorithms for the minimum dominating set problem on some graph classes

Serge Gaspers

Description

Niveau: Supérieur, Doctorat, Bac+8
Exponential time algorithms for the minimum dominating set problem on some graph classes Serge Gaspers University of Bergen Department of Informatics N-5020 Bergen, Norway. Dieter Kratsch Mathieu Liedloff Universite Paul Verlaine LITA F-57045 Metz Cedex 01, France (kratsch|liedloff)@univ-metz.fr Abstract The Minimum Dominating Set problem remains NP-hard when re- stricted to chordal graphs, circle graphs and dense graphs (i.e. |E| ≥ cn2 for a constant c, 0 < c < 1/2). For each of these three classes we present algorithms of time complexities O(?n). More precisely, the algorithm for chordal graphs has running time O(1.4173n), the one for circle graphs runs in time O(1.4956n), and the one for dense graphs is a O(1.2303(1+ √ 1?2c)n) time algorithm. 1 Introduction During the last years there has been a growing interest in the design of exact exponential time algorithms. Woeginger has written a nice survey on the subject [18] emphasizing the major techniques used to design exact exponen- tial time algorithms. We also refer the reader to the recent survey of Fomin et al. [7] discussing some new techniques in the design of exponential time algorithms.

• time algorithms


• has universe


• cover algorithm


• graphs has


• running time


• therefore no bag


• has no chordless


• clique tree

Sujets

• Verlaine
• Running Time
• Tree decomposition

Informations

• Publié par: profil-zyak-2012
• Nombre de lectures: 17
• Langue: English

Extrait

Exponentialtimealgorithmsfortheminimum dominatingsetproblemonsomegraphclasses SergeGaspers UniversityofBergen DepartmentofInformatics N-5020Bergen,Norway. [e-mail] DieterKratschMathieuLiedloff Universite´PaulVerlaine ATIL F-57045MetzCedex01,France (kratsch|liedloff)@univ-metz.fr Abstract TheMinimumDominatingSetproblemremainsNP-hardwhenre- strictedtochordalgraphs,circlegraphsanddensegraphs(i.e. | E |≥ cn 2 foraconstantc,0<c<1/2).Foreachofthesethreeclasses wepresentalgorithmsoftimecomplexitiesO(α n ).Moreprecisely,the algorithmforchordalgraphshasrunningtimeO(1.4173 n ),theonefor circlegraphsrunsintimeO(1.4956 n ),andtheonefordensegraphsis √ aO(1.2303 (1+1 − 2 c ) n )timealgorithm. 1Introduction Duringthelastyearstherehasbeenagrowinginterestinthedesignofexact exponentialtimealgorithms.Woegingerhaswrittenanicesurveyonthe subject[18]emphasizingthemajortechniquesusedtodesignexactexponen- tialtimealgorithms.WealsoreferthereadertotherecentsurveyofFomin etal.[7]discussingsomenewtechniquesinthedesignofexponentialtime algorithms.Theydiscusstreewidthbasedtechniques,Measure&Conquer andmemorization. Knownresults.AsetD⊆VofagraphG=(V,E)isdominating ifeveryvertexofV\DhasaneighborinD.TheMinimumDominating Setproblem (MDS) askstocomputeadominatingsetoftheinputgraphof minimumcardinality. ExactexponentialtimealgorithmsfortheMinimumDominatingSet problemhavenotbeenstudieduntilrecently.Bynowthereisalargeinter- 1