Voir la notice de l'article provenant de la source Numdam
The partial inverse minimum cut problem is to minimally modify the capacities of a digraph such that there exists a minimum cut with respect to the new capacities that contains all arcs of a prespecified set. Orlin showed that the problem is strongly NP-hard if the amount of modification is measured by the weighted L1-norm. We prove that the problem remains hard for the unweighted case and show that the NP-hardness proof of Yang [RAIRO-Oper. Res. 35 (2001) 117-126] for this problem with additional bound constraints is not correct.
@article{RO_2010__44_3_241_0,
author = {Gassner, Elisabeth},
title = {The partial inverse minimum cut problem with {L1-norm} is strongly {NP-hard}},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {241--249},
publisher = {EDP-Sciences},
volume = {44},
number = {3},
year = {2010},
doi = {10.1051/ro/2010017},
mrnumber = {2762795},
zbl = {1206.90141},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ro/2010017/}
}
TY - JOUR AU - Gassner, Elisabeth TI - The partial inverse minimum cut problem with L1-norm is strongly NP-hard JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2010 SP - 241 EP - 249 VL - 44 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ro/2010017/ DO - 10.1051/ro/2010017 LA - en ID - RO_2010__44_3_241_0 ER -
%0 Journal Article %A Gassner, Elisabeth %T The partial inverse minimum cut problem with L1-norm is strongly NP-hard %J RAIRO - Operations Research - Recherche Opérationnelle %D 2010 %P 241-249 %V 44 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ro/2010017/ %R 10.1051/ro/2010017 %G en %F RO_2010__44_3_241_0
Gassner, Elisabeth. The partial inverse minimum cut problem with L1-norm is strongly NP-hard. RAIRO - Operations Research - Recherche Opérationnelle, Tome 44 (2010) no. 3, pp. 241-249. doi: 10.1051/ro/2010017
Cité par Sources :