Approximation hardness of minimum edge dominating set and minimum maximal matching

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-24587-2_43

Approximation hardness of minimum edge dominating set and minimum maximal matching

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

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

219 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 76 . The result extends with negligible loss to bounded degree graphs and to everywhere dense graphs.

Original language	English
Title of host publication	Algorithms and computation
Subtitle of host publication	14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings
Editors	Toshihide Ibaraki, Naoki Katoh, Hirotaka Ono
Place of Publication	Berlin
Publisher	Springer
Pages	415-424
Volume	2906
ISBN (Electronic)	9783540245872
ISBN (Print)	9783540206958
DOIs	https://doi.org/10.1007/978-3-540-24587-2_43
Publication status	Published - 2003

Publication series

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

Keywords

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

Access to Document

10.1007/978-3-540-24587-2_43

Minimum Edge post-print
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-24587-2_43.
Accepted author manuscript (Post-print), 145 KB

Cite this

Chlebik, M., & Chlebikova, J. (2003). Approximation hardness of minimum edge dominating set and minimum maximal matching. In T. Ibaraki, N. Katoh, & H. Ono (Eds.), Algorithms and computation : 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings (Vol. 2906, pp. 415-424). (Lecture Notes in Computer Science; Vol. 2906). Springer. https://doi.org/10.1007/978-3-540-24587-2_43

Chlebik, Miroslav ; Chlebikova, Janka. / Approximation hardness of minimum edge dominating set and minimum maximal matching. Algorithms and computation : 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings. editor / Toshihide Ibaraki ; Naoki Katoh ; Hirotaka Ono. Vol. 2906 Berlin : Springer, 2003. pp. 415-424 (Lecture Notes in Computer Science).

@inproceedings{a1a041b66455473180f9ef20974dbe89,

title = "Approximation hardness of minimum edge dominating set and minimum maximal matching",

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 76 . 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",

note = "The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3-540-24587-2_43]”.",

year = "2003",

doi = "10.1007/978-3-540-24587-2_43",

language = "English",

isbn = "9783540206958",

volume = "2906",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "415--424",

editor = "Toshihide Ibaraki and Naoki Katoh and Hirotaka Ono",

booktitle = "Algorithms and computation",

}

Chlebik, M & Chlebikova, J 2003, Approximation hardness of minimum edge dominating set and minimum maximal matching. in T Ibaraki, N Katoh & H Ono (eds), Algorithms and computation : 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings. vol. 2906, Lecture Notes in Computer Science, vol. 2906, Springer, Berlin, pp. 415-424. https://doi.org/10.1007/978-3-540-24587-2_43

Approximation hardness of minimum edge dominating set and minimum maximal matching. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithms and computation : 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings. ed. / Toshihide Ibaraki; Naoki Katoh; Hirotaka Ono. Vol. 2906 Berlin: Springer, 2003. p. 415-424 (Lecture Notes in Computer Science; Vol. 2906).

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

TY - GEN

T1 - Approximation hardness of minimum edge dominating set and minimum maximal matching

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - The final publication is available at Springer via http://dx.doi.org/[10.1007/978-3-540-24587-2_43]”.

PY - 2003

Y1 - 2003

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 76 . 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 76 . 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/978-3-540-24587-2_43

DO - 10.1007/978-3-540-24587-2_43

M3 - Conference contribution

SN - 9783540206958

VL - 2906

T3 - Lecture Notes in Computer Science

SP - 415

EP - 424

BT - Algorithms and computation

A2 - Ibaraki, Toshihide

A2 - Katoh, Naoki

A2 - Ono, Hirotaka

PB - Springer

CY - Berlin

ER -

Chlebik M, Chlebikova J. Approximation hardness of minimum edge dominating set and minimum maximal matching. In Ibaraki T, Katoh N, Ono H, editors, Algorithms and computation : 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings. Vol. 2906. Berlin: Springer. 2003. p. 415-424. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-24587-2_43

Approximation hardness of minimum edge dominating set and minimum maximal matching

Abstract

Publication series

Keywords

Access to Document

Fingerprint

Cite this