Дальневосточный математический журнал
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Дальневост. матем. журн.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Дальневосточный математический журнал, 2020, том 20, номер 2, страницы 267–270
DOI: https://doi.org/10.47910/FEMJ202027 (Mi dvmg440) 		 
Вычислительная сложность оптимального блокирования вершин в орграфе

Г. Ш. Цициашвили

Институт прикладной математики ДВО РАН, г. Владивосток
PDF полного текста (94 kB)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.47910/FEMJ202027
Аннотация: В настоящей работе решена задача определения минимального набора ребер, удаление которых из орграфа разрывает все пути, проходящие через выделенное множество вершин. Эта задача сведена к задаче о минимальном разрезе и максимальном потоке в двухполюснике. Предложены способы декомпозиции орграфа, уменьшающие вычислительную сложность алгоритма решения данной задачи.
Ключевые слова: орграф, теорема Форда – Фалкерсона, оптимальное блокирование, вычислительная сложность.
Финансовая поддержка Номер гранта
ПФИ ДВО РАН "Дальний Восток" 15-I-4-047
Исследование выполнено при финансовой ПФИ ДВО РАН "Дальний Восток" (проект № 15-I-4-047).
Поступила в редакцию: 11.08.2020
Тип публикации: Статья
УДК: 519.178
MSC: 68R10
Образец цитирования: Г. Ш. Цициашвили, “Вычислительная сложность оптимального блокирования вершин в орграфе”, Дальневост. матем. журн., 20:2 (2020), 267–270
Цитирование в формате AMSBIB
\RBibitem{Tsi20}
\by Г.~Ш.~Цициашвили
\paper Вычислительная сложность оптимального блокирования вершин в орграфе
\jour Дальневост. матем. журн.
\yr 2020
\vol 20
\issue 2
\pages 267--270
\mathnet{http://mi.mathnet.ru/dvmg440}
\crossref{https://doi.org/10.47910/FEMJ202027}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/dvmg440
  • https://www.mathnet.ru/rus/dvmg/v20/i2/p267
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Дальневосточный математический журнал
    Статистика просмотров:
    Страница аннотации:116
    PDF полного текста:42
    Список литературы:18
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024