Far Eastern Mathematical Journal

To content of the issue


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.

To content of the issue