Approximation hardness of minimum edge dominating set and minimum maximal matching

Chlebík, Miroslav and Chlebíková, Janka (2003) Approximation hardness of minimum edge dominating set and minimum maximal matching. In: 14th Annual International Symposium on Algorithms and Computation, Algorithms and Computation, KYOTO, JAPAN.

Full text not available from this repository.

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.

Item Type: Conference or Workshop Item (Paper)
Additional Information: ALGORITHMS AND COMPUTATION, PROCEEDINGS
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 19:14
Last Modified: 04 Apr 2012 08:13
URI: http://sro.sussex.ac.uk/id/eprint/19663
📧 Request an update