Chlebík, Miroslav and Chlebíková, Janka (2006) Approximation hardness of edge dominating set problems. Journal of Combinatorial Optimization, 11 (3). pp. 279-290. ISSN 1382-6905

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:	Article
Schools and Departments:	School of Mathematical and Physical Sciences > Mathematics
Depositing User:	Miroslav Chlebik
Date Deposited:	06 Feb 2012 19:09
Last Modified:	03 Apr 2012 15:07
URI:	http://sro.sussex.ac.uk/id/eprint/19442

📧 Request an update