The Disjoint Path Problem With The Most Vital Node And Arc

Multipath Routing plays an important role in the communication network. To com-pare with the single path routing, Multipath Routing can increase the reliability of a net-work, avoid congestion and reduce the probability of dropped packets. Disjoint pathsprovide the primary approach for Multipath Routing. In this paper, we give some simplealgorithms for the disjoint path problem. In addition, as different nodes and arcs playdifferent roles in the network，we propose the most vital node and arc problem of thedisjoint path problem and present the corresponding algorithm. We lay a good foundationfor Multipath Routing.The main achievements of this paper are as follows.1．We give an algorithm for the shortest pair of disjoint path problem and prove itcompactly.2．We present a new question that is how to find the largest number of disjoint pathswhich exist synchronously in the network. And we consider how to get K(K is an integerand K>1) disjoint paths whose total weights are the least. We discover the connectionbetween the disjoint paths and the network flow. Benefiting from the network flow, wegive some simple algorithms for the two kinds of questions.3．We propose the most vital node and arc problem of the disjoint path problem.Then we introduce the concept of vital-degree and prove the vital-degree of a node iscorrelated with its out-degree, based on which, we design an algorithm to find the mostvital node of the arc-disjoint path number problem. According to its own characteristicsof the arc-disjoint path number problem, we give some methods for finding the most vitalarc 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 theoryof network flow to construct the replacement path. After transforming the network, wefindthemostvitalnodeandarcofthe K node-disjointpathproblembythesimilarlyway.