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/