Approximation hardness of edge dominating set problems

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/s10878-006-7908-0

Approximation hardness of edge dominating set problems

Miroslav Chlebik
, Janka Chlebikova

University of Sussex

Research output: Contribution to journal › Article › peer-review

705 Downloads (Pure)

Abstract

We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, Minimum Edge Dominating Set and Minimum Maximal Matching. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than 7/6. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

Original language	English
Pages (from-to)	279--290
Journal	Journal of Combinatorial Optimisation
Volume	11
Issue number	3
DOIs	https://doi.org/10.1007/s10878-006-7908-0
Publication status	Published - May 2006

Keywords

minimum edge dominating set
minimum maximal matching
approximation lower bound
bounded degree graphs
everywhere dense graphs

Access to Document

10.1007/s10878-006-7908-0

MATCHING_JOURNAL-reviewAccepted author manuscript (Post-print), 182 KB

Cite this

@article{2759347dcc3e48f6a6a40b943e7fb377,

title = "Approximation hardness of edge dominating set problems",

abstract = "We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, Minimum Edge Dominating Set and Minimum Maximal Matching. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than 7/6. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.",

keywords = "minimum edge dominating set, minimum maximal matching, approximation lower bound, bounded degree graphs, everywhere dense graphs",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2006",

month = may,

doi = "10.1007/s10878-006-7908-0",

language = "English",

volume = "11",

pages = "279----290",

journal = "Journal of Combinatorial Optimisation",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Approximation hardness of edge dominating set problems

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2006/5

Y1 - 2006/5

N2 - We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, Minimum Edge Dominating Set and Minimum Maximal Matching. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than 7/6. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

AB - We provide the first interesting explicit lower bounds on efficient approximability for two closely related optimization problems in graphs, Minimum Edge Dominating Set and Minimum Maximal Matching. We show that it is NP-hard to approximate the solution of both problems to within any constant factor smaller than 7/6. The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

KW - minimum edge dominating set

KW - minimum maximal matching

KW - approximation lower bound

KW - bounded degree graphs

KW - everywhere dense graphs

U2 - 10.1007/s10878-006-7908-0

DO - 10.1007/s10878-006-7908-0

M3 - Article

SN - 1382-6905

VL - 11

SP - 279

EP - 290

JO - Journal of Combinatorial Optimisation

JF - Journal of Combinatorial Optimisation

IS - 3

ER -

Approximation hardness of edge dominating set problems

Abstract

Keywords

Access to Document

Fingerprint

Cite this