15 Pages
English

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

-

Gain access to the library to view online
Learn more

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


Subjects

Informations

Published by
Reads 17
Language English
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