Chlebik, Miroslav and Chlebíková, Janka (2004) On approximability of the independent set problem for low degree graphs. In: 11th International Colloquium on Structural Information and Communication Complexity, Smolenice, SLOVAKIA.

Full text not available from this repository.

Abstract

We obtain slightly improved upper bounds on efficient approximability of the MAXIMUM INDEPENDENT SET problem in graphs of maximum degree at most B (shortly, B-MAXIS), for small B > 3. The degree-three case plays a role of the central problem, as many of the results for the other problems use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-MAXIS shows that one can achieve approximation ratio arbitrarily close to 3 - root13/2. Improvements of an approximation ratio below for this case trans late to improvements below B+3/5 of approximation factors for B-MAXIS for all odd B. Consequently, for any odd B greater than or equal to 3, polynomial time algorithms for B-MAXIS exist with approximation ratios arbitrarily close to B+3/5 - 4(5root13-18)/5 (B-2)!!/(B-2)!!. This is currently the best upper bound for B-MAXIS for any odd B, 3 less than or equal to B < 613.

Item Type:	Conference or Workshop Item (Paper)
Additional Information:	STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDING
Schools and Departments:	School of Mathematical and Physical Sciences > Mathematics
Depositing User:	Miroslav Chlebik
Date Deposited:	06 Feb 2012 18:24
Last Modified:	03 Apr 2012 12:39
URI:	http://sro.sussex.ac.uk/id/eprint/16143

📧 Request an update