Pairs of Arc-Disjoint Paths in a Network

摘要

Two methods for finding suboptimal arc-disjoint paths between two given nodes of a network are discussed and compared to an existing optimal (minimum cost) method. Computation time for both methods are shorter than the optimal method and a computer experiment shows that for one of the methods the probability of cost coincidence with the optimal method is close to one for a sufficiently large number of the network nodes. The problems of finding the optimal pair of arc-disjoint paths with a unique source (or destination) is also discussed.