Exact (exponential) algorithms for the dominating set problem

Fedor V. Fomin, Dieter Kratsch, Gerhard J. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

76 Citations (Scopus)

Abstract

We design fast exact algorithms for the problem of computing a minimum dominating set in undirected graphs. Since this problem is NP-hard, it comes with no big surprise that all our time complexities are exponential in the number n of vertices. The contribution of this paper are ‘nice’ exponential time complexities that are bounded by functions of the form c n with reasonably small constants c<2: For arbitrary graphs we get a time complexity of 1.93782 n . And for the special cases of split graphs, bipartite graphs, and graphs of maximum degree three, we reach time complexities of 1.41422 n , 1.73206 n , and 1.51433 n , respectively.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers
EditorsJuraj Hromkovic, Manfred Nagl, Bernhard Westfechtel
Place of PublicationHeidelberg
PublisherSpringer
Pages245-256
ISBN (Electronic)978-3-540-30559-0
ISBN (Print)978-3-540-24132-4
DOIs
Publication statusPublished - 21 Jun 2004
Event30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany
Duration: 21 Jun 200423 Jun 2004
Conference number: 30

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume3353
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated titleWG
CountryGermany
CityBad Honnef
Period21/06/0423/06/04

Keywords

  • METIS-219806

Fingerprint

Dive into the research topics of 'Exact (exponential) algorithms for the dominating set problem'. Together they form a unique fingerprint.

Cite this