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
Type
Article accepté pour publication ou publiéExternal document link
https://hal.archives-ouvertes.fr/hal-00003926Date
2003Journal name
Operations Research LetterVolume
31Number
3Pages
195-201
Metadata
Show full item recordAbstract (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 / Keywords
Hereditary property; APX-complete; Maximum subgraph problem; Minimum vertex deletion problem; Aproximation algorithms; Local searchRelated items
Showing items related by title and author.
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2004) Article accepté pour publication ou publié
-
Boria, Nicolas; Monnot, Jérôme; Paschos, Vangelis (2012) Communication / Conférence
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Ouvrage
-
Paschos, Vangelis; Monnot, Jérôme; Toulouse, Sophie (2003) Article accepté pour publication ou publié
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié