Sun, Zhishuai; Xie, Zheng Finding one of the most vital nodes and arcs of the disjoint path problem. (Chinese. English summary) Zbl 1313.05346 Acta Math. Appl. Sin. 37, No. 3, 516-526 (2014). Summary: For the disjoint path number problem, we introduce the concept of vital-degree and prove that the vital-degree of a node is correlated with its out-degree, based on which, we design an algorithm to find the most vital node of the arc-disjoint path problem. According to its own characteristics of the arc-disjoint path problem, we give some methods for finding the most vital arc of the arc-disjoint path number problem and the most vital node and arc of the node-disjoint path number problem. For the \(K\)-arc-disjoint path problem, we utilize the theory of network flow to construct the replacement path. After transforming the network, we find the most vital node and arc of the \(K\)-node-disjoint path problem by a similar way. In addition, we give some examples in the last section of the paper. MSC: 05C85 Graph algorithms (graph-theoretic aspects) 90B18 Communication networks in operations research Keywords:disjoint path; most vital node; most vital arc PDFBibTeX XMLCite \textit{Z. Sun} and \textit{Z. Xie}, Acta Math. Appl. Sin. 37, No. 3, 516--526 (2014; Zbl 1313.05346)