Approximation hardness of dominating set problems

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-30140-0_19

Approximation hardness of dominating set problems

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.

Original language	English
Title of host publication	Algorithms – ESA 2004
Subtitle of host publication	12th annual European symposium, Bergen, Norway, September 14-17, 2004. proceedings
Editors	Susanne Albers, Tomasz Radzik
Place of Publication	Berlin
Publisher	Springer
Pages	192-203
Volume	3221
ISBN (Electronic)	9783540301400
ISBN (Print)	9783540230250
DOIs	https://doi.org/10.1007/978-3-540-30140-0_19
Publication status	Published - 2004

Publication series

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

Access to Document

10.1007/978-3-540-30140-0_19

Cite this

@inproceedings{c5057ba9c6db4150938edc7deca75068,

title = "Approximation hardness of dominating set problems",

abstract = "We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2004",

doi = "10.1007/978-3-540-30140-0_19",

language = "English",

isbn = "9783540230250",

volume = "3221",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "192--203",

editor = "Susanne Albers and Tomasz Radzik",

booktitle = "Algorithms – ESA 2004",

}

Approximation hardness of dominating set problems. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithms – ESA 2004: 12th annual European symposium, Bergen, Norway, September 14-17, 2004. proceedings. ed. / Susanne Albers; Tomasz Radzik. Vol. 3221 Berlin : Springer, 2004. p. 192-203 (Lecture Notes in Computer Science; Vol. 3221).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Approximation hardness of dominating set problems

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2004

Y1 - 2004

N2 - We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.

AB - We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.

U2 - 10.1007/978-3-540-30140-0_19

DO - 10.1007/978-3-540-30140-0_19

M3 - Conference contribution

SN - 9783540230250

VL - 3221

T3 - Lecture Notes in Computer Science

SP - 192

EP - 203

BT - Algorithms – ESA 2004

A2 - Albers, Susanne

A2 - Radzik, Tomasz

PB - Springer

CY - Berlin

ER -

Approximation hardness of dominating set problems

Abstract

Publication series

Access to Document

Fingerprint

Cite this