Exact (exponential) algorithms for the dominating set problem

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

doi:10.1007/978-3-540-30559-0_21

Exact (exponential) algorithms for the dominating set problem

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

Discrete Mathematics and Mathematical Programming

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

98 Citations (Scopus)

10 Downloads (Pure)

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 language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science
Subtitle of host publication	30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers
Editors	Juraj Hromkovic, Manfred Nagl, Bernhard Westfechtel
Place of Publication	Heidelberg
Publisher	Springer
Pages	245-256
ISBN (Electronic)	978-3-540-30559-0
ISBN (Print)	978-3-540-24132-4
DOIs	https://doi.org/10.1007/978-3-540-30559-0_21
Publication status	Published - 21 Jun 2004
Event	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004 - Bad Honnef, Germany Duration: 21 Jun 2004 → 23 Jun 2004 Conference number: 30

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	3353
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004
Abbreviated title	WG
Country/Territory	Germany
City	Bad Honnef
Period	21/06/04 → 23/06/04

Keywords

METIS-219806

Access to Document

10.1007/978-3-540-30559-0_21

Cite this

Fomin, F. V., Kratsch, D., & Woeginger, G. J. (2004). Exact (exponential) algorithms for the dominating set problem. In J. Hromkovic, M. Nagl, & B. Westfechtel (Eds.), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers (pp. 245-256). (Lecture Notes in Computer Science; Vol. 3353). Springer. https://doi.org/10.1007/978-3-540-30559-0_21

Fomin, Fedor V. ; Kratsch, Dieter ; Woeginger, Gerhard J. / Exact (exponential) algorithms for the dominating set problem. Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. editor / Juraj Hromkovic ; Manfred Nagl ; Bernhard Westfechtel. Heidelberg : Springer, 2004. pp. 245-256 (Lecture Notes in Computer Science).

@inproceedings{c7271fecde0842b48839634f50c1b45c,

title = "Exact (exponential) algorithms for the dominating set problem",

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 {\textquoteleft}nice{\textquoteright} 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.",

keywords = "METIS-219806",

author = "Fomin, {Fedor V.} and Dieter Kratsch and Woeginger, {Gerhard J.}",

year = "2004",

month = jun,

day = "21",

doi = "10.1007/978-3-540-30559-0_21",

language = "English",

isbn = "978-3-540-24132-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "245--256",

editor = "Juraj Hromkovic and Manfred Nagl and Bernhard Westfechtel",

booktitle = "Graph-Theoretic Concepts in Computer Science",

address = "Germany",

note = "30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, WG ; Conference date: 21-06-2004 Through 23-06-2004",

}

Fomin, FV, Kratsch, D & Woeginger, GJ 2004, Exact (exponential) algorithms for the dominating set problem. in J Hromkovic, M Nagl & B Westfechtel (eds), Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. Lecture Notes in Computer Science, vol. 3353, Springer, Heidelberg, pp. 245-256, 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004, Bad Honnef, Germany, 21/06/04. https://doi.org/10.1007/978-3-540-30559-0_21

Exact (exponential) algorithms for the dominating set problem. / Fomin, Fedor V.; Kratsch, Dieter; Woeginger, Gerhard J.
Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. ed. / Juraj Hromkovic; Manfred Nagl; Bernhard Westfechtel. Heidelberg: Springer, 2004. p. 245-256 (Lecture Notes in Computer Science; Vol. 3353).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Exact (exponential) algorithms for the dominating set problem

AU - Fomin, Fedor V.

AU - Kratsch, Dieter

AU - Woeginger, Gerhard J.

N1 - Conference code: 30

PY - 2004/6/21

Y1 - 2004/6/21

N2 - 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.

AB - 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.

KW - METIS-219806

U2 - 10.1007/978-3-540-30559-0_21

DO - 10.1007/978-3-540-30559-0_21

M3 - Conference contribution

SN - 978-3-540-24132-4

T3 - Lecture Notes in Computer Science

SP - 245

EP - 256

BT - Graph-Theoretic Concepts in Computer Science

A2 - Hromkovic, Juraj

A2 - Nagl, Manfred

A2 - Westfechtel, Bernhard

PB - Springer

CY - Heidelberg

T2 - 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004

Y2 - 21 June 2004 through 23 June 2004

ER -

Fomin FV, Kratsch D, Woeginger GJ. Exact (exponential) algorithms for the dominating set problem. In Hromkovic J, Nagl M, Westfechtel B, editors, Graph-Theoretic Concepts in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004. Revised Papers. Heidelberg: Springer. 2004. p. 245-256. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-30559-0_21

Exact (exponential) algorithms for the dominating set problem

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this