File(s) not publicly available
Approximation hardness of edge dominating set problems
journal contribution
posted on 2023-06-07, 22:07 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková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.
History
Publication status
- Published
Journal
Journal of Combinatorial OptimizationISSN
1382-6905Publisher
SPRINGERExternal DOI
Issue
3Volume
11Page range
279-290Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC