A quick method for finding shortest pairs of disjoint paths

J. W. Suurballe, R. E. Tarjan

Research output: Contribution to journalArticle

521 Scopus citations

Abstract

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(n2 logn)‐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.

Original languageEnglish (US)
Pages (from-to)325-336
Number of pages12
JournalNetworks
Volume14
Issue number2
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'A quick method for finding shortest pairs of disjoint paths'. Together they form a unique fingerprint.

  • Cite this