作者
Francois Delbot, Christian Laforest, Raksmey Phan
发表日期
2015/6/2
研讨会论文
ALGOTEL 2015—17èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications
简介
Une instance du problème est un graphe, un ensemble F de sommets interdits et un ensemble R de sommets obligatoires. Nous montrons que construire un vertex cover, connexe ou pas, de taille minimale, contenant tous les sommets de R et aucun sommet de F, peut être 2-approché (s' il existe). Nous montrons aussi que décider s' il existe ou pas un ensemble dominant indépendant contenant tout R et aucun sommet de F est NP-complet.
学术搜索中的文章
F Delbot, C Laforest, R Phan - … 2015—17èmes Rencontres Francophones sur les …, 2015