Approximation hardness of dominating set problems

Chlebík, Miroslav and Chlebíková, Janka (2004) Approximation hardness of dominating set problems. In: 12th Annual European Symposium on Algorithms (ESA 2004), Bergen, NORWAY.

Full text not available from this repository.


We study approximation hardness of the MINIMUM DOMINATING SET problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the MAXIMUM INDUCED MATCHING problem and the MAXIMUM LEAF SPANNING TREE problem.

Item Type: Conference or Workshop Item (Paper)
Additional Information: Lecture Notes in Computer Science, Algorithms ESA 2004
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 20:11
Last Modified: 04 Apr 2012 12:35
📧 Request an update