Approximation hardness of dominating set problems in bounded degree graphs

Chlebík, M and Chlebíková, J (2008) Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, 206 (11). pp. 1264-1275. ISSN 0890-5401

Full text not available from this repository.

Abstract

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. Using a similar result obtained by Trevisan for Minimum Set Cover we prove the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. Asymptotically, for degree bound approaching infinity, these bounds almost match the known upper bounds. The results are applied to improve the lower bounds for other related problems such as Maximum Induced Matching and Maximum Leaf Spanning Tree.

Item Type: Article
Schools and Departments: School of Mathematical and Physical Sciences > Mathematics
Depositing User: Miroslav Chlebik
Date Deposited: 06 Feb 2012 20:15
Last Modified: 04 Apr 2012 12:53
URI: http://sro.sussex.ac.uk/id/eprint/25009
📧 Request an update