An effective algorithm for obtaining the whole set of minimal cost pairs of disjoint paths with dual arc costs

In telecommunication networks design the problem of obtaining optimal (arc or node) disjoint paths, for increasing network reliability, is extremely important. The problem of calculating k _c disjoint paths from s to t (two distinct nodes), in a network with k _c different (arbitrary) costs on every arc such that the total cost of the paths is minimised, is NP-complete even for k _c =2. When k _c =2 these networks are usually designated as dual arc cost networks.