Дальневосточный математический журнал

К содержанию выпуска


Вычислительная сложность оптимального блокирования вершин в орграфе


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

2020, выпуск 2, С. 267–270
DOI: https://doi.org/10.47910/FEMJ202027


Аннотация
В настоящей работе решена задача определения минимального набора ребер, удаление которых из орграфа разрывает все пути, проходящие через выделенное множество вершин. Эта задача сведена к задаче о минимальном разрезе и максимальном потоке в двухполюснике. Предложены способы декомпозиции орграфа, уменьшающие вычислительную сложность алгоритма решения данной задачи.

Ключевые слова: орграф, теорема Форда – Фалкерсона, оптимальное блокирование, вычислительная сложность

Полный текст статьи (файл PDF)

Библиографический список

[1] L. R. Ford, D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics, 8, (1956), 399–404.
[2] L. R. Ford, D. R. Fulkerson, “Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem”, Canadian Journal of Mathematics, 9, (1957), 210–218.
[3] G. Sh. Tsitsiashvili, “Optimal blocking of undesired nodes in digraph”, Annals of Biostatistics and Biometric Applications, 4:1, (2020).
[4] J. Edmonds and R. M. Karp, “Theoretical Improvements in Algorithmic E?ciency for Network Flow Problems”, Journal of the ACM, 19:2, (1972), 248–264.
[5] E. A. Dinits, “Algorithm for solving the problem of maximum ?ow in the network with power estimation”, Reports of the USSR Academy of Sciences (In Russian), 194:4, (1970), 754–757.
[6] G. Sh. Tsitsiashvili, “Sequential algorithms of graph nodes factorization”, Reliability: The- ory and Applications, 8:4, (2013), 30–33.

К содержанию выпуска