The computational complexity of optimal blocking of vertices in the digraph

DOI10.47910/FEMJ202027MaRDI QIDQ5151321zbMATH OpenFDO

Authors G. Sh. Tsitsiashvili

Publication date 17 February 2021

Published in Dal'nevostochnyi Matematicheskii Zhurnal (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/dvmg440

zbMATH Keywords

computational complexitydigraphFord-Fulkerson theoremoptimal blocking

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 176397
• Optimal Reduction of Two-Terminal Directed Acyclic Graphs
• scientific article; zbMATH DE number 3910419
• Determination of the tree of minimax paths in a weighted digraph
• On the computational complexity of path cover problems

Cites work

• A Simple Algorithm for Finding Maximal Network Flows and an Application to the Hitchcock Problem
• scientific article; zbMATH DE number 3349645 (Why is no real title available?)
• Maximal Flow Through a Network
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(8)

• Exact algorithms for the minimum cost vertex blocker clique problem
• A linear time algorithm for the nullity of vertex-weighted block graphs
• Graph complexity and the laplacian matrix in blocked experiments
• Capacity complexity of the accessibility problem for frontally bounded digraphs
• scientific article; zbMATH DE number 176397 (Why is no real title available?)
• On the optimal strategy for an isotropic blocking problem
• scientific article; zbMATH DE number 5060433 (Why is no real title available?)
• The complexity of node blocking for dags

This page was built for publication: The computational complexity of optimal blocking of vertices in the digraph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5151321)