Geodesic
On Stable Instances of MINCUT
Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 54-63

Voir la notice de l'article provenant de la source Math-Net.Ru

A combinatorial optimization problem is called stable if its solution is preserved under perturbation of the input parameters that do not exceed a certain threshold — the stability radius. In [1–3] exact polynomial algorithms have been built for some NP-hard problems on cuts in the assumption of the entrance stability. In this paper we show how to accelerate some algorithms for sufficiently stable polynomial problems. The approach is illustrated by the well-known problem of the minimum cut (MINCUT). We built an $ O(n^2)$ exact algorithm for solving $n$-stable instance of the MINCUT problem. Moreover, we present a polynomial algorithm for calculating the stability radius and a simple criterion for checking $n$-stability of the MINCUT problem.
Keywords: stability
Mots-clés : mincut. 
@article{MAIS_2014_21_4_a5,
     author = {I. V. Kozlov},
     title = {On {Stable} {Instances} of {MINCUT}},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {54--63},
     publisher = {mathdoc},
     volume = {21},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a5/}
}
TY  - JOUR
AU  - I. V. Kozlov
TI  - On Stable Instances of MINCUT
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2014
SP  - 54
EP  - 63
VL  - 21
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a5/
LA  - ru
ID  - MAIS_2014_21_4_a5
ER  - 
%0 Journal Article
%A I. V. Kozlov
%T On Stable Instances of MINCUT
%J Modelirovanie i analiz informacionnyh sistem
%D 2014
%P 54-63
%V 21
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a5/
%G ru
%F MAIS_2014_21_4_a5
I. V. Kozlov. On Stable Instances of MINCUT. Modelirovanie i analiz informacionnyh sistem, Tome 21 (2014) no. 4, pp. 54-63. http://geodesic.mathdoc.fr/item/MAIS_2014_21_4_a5/