Local approximations for maximum partial subgraph problem期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

Local approximations for maximum partial subgraph problem

Authors:	Jé rô me Monnot^{,Vangelis Th. Paschos}

Affiliation:	LAMSADE, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris, Cedex 16, France

Abstract:	We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H₀)d_H₀(v) and ν₀=(\|V(H₀)\|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.

Keywords:	Approximation algorithms Local search APX-complete Maximum subgraph problem Minimum vertex deletion problem Hereditary property
本文献已被 ScienceDirect 等数据库收录！