×

Finding one of the most vital nodes and arcs of the disjoint path problem. (Chinese. English summary) Zbl 1313.05346

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
PDFBibTeX XMLCite