×

The computational complexity of optimal blocking of vertices in the digraph. (Russian. English summary) Zbl 1462.68149

Summary: 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.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C20 Directed graphs (digraphs), tournaments
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI MNR

References:

[1] L. R. Ford, D. R. Fulkerson, “Maximal Flow Through a Network”, Canadian Journal of Mathematics, 8 (1956), 399-404 · Zbl 0073.40203
[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 · Zbl 0088.12907
[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 · Zbl 0318.90024
[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 · Zbl 0219.90046
[6] G. Sh. Tsitsiashvili, “Sequential algorithms of graph nodes factorization”, Reliability: Theory and Applications, 8:4 (2013), 30-33
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.