Approximation hardness of edge dominating set problems

Miroslav Chlebik, Janka Chlebikova

Research output: Contribution to journalArticlepeer-review

159 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 languageEnglish
Pages (from-to)279--290
JournalJournal of Combinatorial Optimisation
Volume11
Issue number3
DOIs
Publication statusPublished - May 2006

Keywords

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

Fingerprint

Dive into the research topics of 'Approximation hardness of edge dominating set problems'. Together they form a unique fingerprint.

Cite this