FAR EASTERN BRANCH OF THE RUSSIAN ACADEMY OF SCIENCES
INSTITUTE OF APPLIED MATHEMATICS KHABAROVSK DIVISION
Far Eastern Mathematical Journal
The computational complexity of optimal blocking of vertices in the digraph |
Tsitsiashvili G.Sh. |
2020, issue 2, P. 267–270 DOI: https://doi.org/10.47910/FEMJ202027 |
Abstract |
| In this paper, we solve the problem of determining the minimum set of edges, whose removal from the digraph breaks all paths, that pass through the selected set of vertices. This problem is reduced to the problem of the minimum section and maximum flow in a bipolar junction. Methods of digraph decomposition that reduce its computational complexity are proposed. |
Keywords: digraph, Ford-Fulkerson Theorem, optimal blocking, computational complexity |
Download the article (PDF-file) |
References |
| [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. |