Geodesic
The computational complexity of optimal blocking of vertices in the digraph
Dalʹnevostočnyj matematičeskij žurnal, Tome 20 (2020) no. 2, pp. 267-270.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DVMG_2020_20_2_a14,
     author = {G. Sh. Tsitsiashvili},
     title = {The computational complexity of optimal blocking of vertices in the digraph},
     journal = {Dalʹnevosto\v{c}nyj matemati\v{c}eskij \v{z}urnal},
     pages = {267--270},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DVMG_2020_20_2_a14/}
}
TY  - JOUR
AU  - G. Sh. Tsitsiashvili
TI  - The computational complexity of optimal blocking of vertices in the digraph
JO  - Dalʹnevostočnyj matematičeskij žurnal
PY  - 2020
SP  - 267
EP  - 270
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DVMG_2020_20_2_a14/
LA  - ru
ID  - DVMG_2020_20_2_a14
ER  - 
%0 Journal Article
%A G. Sh. Tsitsiashvili
%T The computational complexity of optimal blocking of vertices in the digraph
%J Dalʹnevostočnyj matematičeskij žurnal
%D 2020
%P 267-270
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DVMG_2020_20_2_a14/
%G ru
%F DVMG_2020_20_2_a14
G. Sh. Tsitsiashvili. The computational complexity of optimal blocking of vertices in the digraph. Dalʹnevostočnyj matematičeskij žurnal, Tome 20 (2020) no. 2, pp. 267-270. http://geodesic.mathdoc.fr/item/DVMG_2020_20_2_a14/

[1] L. R. Ford, D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics, 8 (1956), 399–404 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[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 Efficiency for Network Flow Problems”, Journal of the ACM, 19:2 (1972), 248–-264 | DOI | MR | Zbl

[5] E. A. Dinits, “Algorithm for solving the problem of maximum flow in the network with power estimation”, Reports of the USSR Academy of Sciences (In Russian), 194:4 (1970), 754–-757 | MR | Zbl

[6] G. Sh. Tsitsiashvili, “Sequential algorithms of graph nodes factorization”, Reliability: Theory and Applications, 8:4 (2013), 30–33