Local approximations for maximum partial subgraph problem
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2004), Local approximations for maximum partial subgraph problem, Operations Research Letters, 32, 3, p. 217-224. http://dx.doi.org/10.1016/j.orl.2003.08.004
TypeArticle accepté pour publication ou publié
Journal nameOperations Research Letters
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 / KeywordsApproximation algorithms; APX-complete; Maximum subgraph problem; Minimum vertex deletion problem; Hereditary property
Showing items related by title and author.