Local approximation for maximum H0-free partial subgraph problems
Monnot, Jérôme; Paschos, Vangelis; Toulouse, S. (2003), Local approximation for maximum H0-free partial subgraph problems, Operations Research Letter, 31, 3, p. 195-201
TypeArticle accepté pour publication ou publié
External document linkhttps://hal.archives-ouvertes.fr/hal-00003926
Journal nameOperations Research Letter
MetadataShow full item record
Abstract (EN)We deal with max H0-free partial subgraph. We mainly prove that 3-locally optimal solutions achieve approximation ratio (d0+1)/(B+2+n0), where B is the maximum degree on G, d0 the minimum degree on H0, and n0 = (|V(H0)|+1)/d0. Next, we show that this ratio rises up to 3/(B+1) when H0 = K3. Finally, we provide hardness results for max K3-free partial subgraph.
Subjects / KeywordsHereditary property; APX-complete; Maximum subgraph problem; Minimum vertex deletion problem; Aproximation algorithms; Local search
Showing items related by title and author.