RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Model. Anal. Inform. Sist., 2014, Volume 21, Number 4, Pages 54–63 (Mi mais387)  

This article is cited in 1 scientific paper (total in 1 paper)

On Stable Instances of MINCUT

I. V. Kozlov

Moscow Institute of Physics and Technology, Institutskiy pereulok, 9, Dolgoprudny, Moscow region, 141700, Russia

Abstract: 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, mincut.

Full text: PDF file (434 kB)
References: PDF file   HTML file
UDC: 519.174.1
Received: 02.05.2014

Citation: I. V. Kozlov, “On Stable Instances of MINCUT”, Model. Anal. Inform. Sist., 21:4 (2014), 54–63

Citation in format AMSBIB
\Bibitem{Koz14}
\by I.~V.~Kozlov
\paper On Stable Instances of MINCUT
\jour Model. Anal. Inform. Sist.
\yr 2014
\vol 21
\issue 4
\pages 54--63
\mathnet{http://mi.mathnet.ru/mais387}


Linking options:
  • http://mi.mathnet.ru/eng/mais387
  • http://mi.mathnet.ru/eng/mais/v21/i4/p54

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. K. G. Kuzmin, “A united approach to finding the stability radii in a multicriteria problem of a maximum cut”, J. Appl. Industr. Math., 9:4 (2015), 527–539  mathnet  crossref  crossref  mathscinet  elib
  • Моделирование и анализ информационных систем
    Number of views:
    This page:279
    Full text:98
    References:35

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020