Premium
A quick method for finding shortest pairs of disjoint paths
Author(s) -
Suurballe J. W.,
Tarjan R. E.
Publication year - 1984
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230140209
Subject(s) - combinatorics , disjoint sets , mathematics , vertex (graph theory) , binary logarithm , floyd–warshall algorithm , graph , time complexity , enhanced data rates for gsm evolution , discrete mathematics , shortest path problem , computer science , dijkstra's algorithm , telecommunications
Let G be a directed graph containing n vertices, one of which is a distinguished source s , and m edges, each with a non‐negative cost. We consider the problem of finding, for each possible sink vertex v , a pair of edge‐disjoint paths from s to v of minimum total edge cost. Suurballe has given an O ( n 2 log n )‐time algorithm for this problem. We give an implementation of Suurballe's algorithm that runs in O ( m log( 1+ m/n ) n ) time and O ( m ) space. Our algorithm builds an implicit representation of the n pairs of paths; given this representation, the time necessary to explicitly construct the pair of paths for any given sink is O (1) per edge on the paths.