|
|||||
|
|
Local approximations for maximum partial subgraph problem |
|
| Authors: | Jérôme Monnot Vangelis Th Paschos |
| Institution: | LAMSADE, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris, Cedex 16, France |
| Abstract: | We deal with MAXH0-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ0+1)/(B+2+ν0), where B=maxv∈VdG(v), δ0=minv∈V(H0)dH0(v) and ν0=(|V(H0)|+1)/δ0. Next, we show that this ratio rises up to 3/(B+1) when H0=K3. Finally, we provide hardness results for MAXK3-FREE PARTIAL SUBGRAPH. |
| Keywords: | Approximation algorithms Local search APX-complete Maximum subgraph problem Minimum vertex deletion problem Hereditary property |
| 本文献已被 ScienceDirect 等数据库收录！ | |