Approximation hardness of minimum edge dominating set and minimum maximal matching

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

142 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 languageEnglish
Title of host publicationAlgorithms and computation
Subtitle of host publication14th international symposium, ISAAC 2003, Kyoto, Japan, December 15-17, 2003. proceedings
EditorsToshihide Ibaraki, Naoki Katoh, Hirotaka Ono
Place of PublicationBerlin
PublisherSpringer
Pages415-424
Volume2906
ISBN (Electronic)9783540245872
ISBN (Print)9783540206958
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume2906
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

Fingerprint

Dive into the research topics of 'Approximation hardness of minimum edge dominating set and minimum maximal matching'. Together they form a unique fingerprint.

Cite this