IEEE Communications Letters · 2010 · 31 citations · 6 references
ComputingComputer ScienceFault ToleranceFault-tolerant ComputingFault-tolerant SystemsCommunication NetworksGraph AlgorithmsGraph TheoryNetwork Flow AlgorithmsNetwork FlowsShortest Path AlgorithmsNetwork Flow ModelsNetwork Flow ProblemsPath DiversityPolynomial Time ComplexityPolynomial-time AlgorithmsResilient Communication NetworksShortest Path ProblemsShortest Paths
In the paper we consider a flow problem closely related to path diversity protection in communication networks. Given a weighted directed graph where some arcs are subject to failures while others are resilient, we aim at computing a shortest pair of failure-disjoint paths. If a resilient arc is used by both paths, its cost is counted only once. We present an original polynomial-time algorithm for solving the problem.
6
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Network flows: Theory, algorithms and applications
Discrete Applied Mathematics · 1994 · 2.6K citations
A quick method for finding shortest pairs of disjoint paths
J. W. Suurballe, Robert E. Tarjan · Networks · 1984 · 693 citations
Resilience in multilayer networks
Piet Demeester, Michaël Gryseels, Achim Autenrieth et al. · IEEE Communications Magazine · 1999 · 200 citations