Exponential time algorithms for the minimum dominating set problem on some graph classes
15 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

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

-

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
15 pages
English

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

Informations

Publié par
Nombre de lectures 17
Langue English

Exrait

ExponentialtimealgorithmsfortheminimumdominatingsetproblemonsomegraphclassesSergeGaspersUniversityofBergenDepartmentofInformaticsN-5020Bergen,Norway.gaspers@ii.uib.noDieterKratschMathieuLiedloUniversite´PaulVerlaineATILF-57045MetzCedex01,France(kratsch|liedloff)@univ-metz.frAbstractTheMinimumDominatingSetproblemremainsNP-hardwhenre-strictedtochordalgraphs,circlegraphsanddensegraphs(i.e.|E|≥cn2foraconstantc,0<c<1/2).ForeachofthesethreeclasseswepresentalgorithmsoftimecomplexitiesO(αn).Moreprecisely,thealgorithmforchordalgraphshasrunningtimeO(1.4173n),theoneforcirclegraphsrunsintimeO(1.4956n),andtheonefordensegraphsisaO(1.2303(1+12c)n)timealgorithm.1IntroductionDuringthelastyearstherehasbeenagrowinginterestinthedesignofexactexponentialtimealgorithms.Woegingerhaswrittenanicesurveyonthesubject[18]emphasizingthemajortechniquesusedtodesignexactexponen-tialtimealgorithms.WealsoreferthereadertotherecentsurveyofFominetal.[7]discussingsomenewtechniquesinthedesignofexponentialtimealgorithms.Theydiscusstreewidthbasedtechniques,Measure&Conquerandmemorization.Knownresults.AsetDVofagraphG=(V,E)isdominatingifeveryvertexofV\DhasaneighborinD.TheMinimumDominatingSetproblem(MDS)askstocomputeadominatingsetoftheinputgraphofminimumcardinality.ExactexponentialtimealgorithmsfortheMinimumDominatingSetproblemhavenotbeenstudieduntilrecently.Bynowthereisalargeinter-1