On a Second Shortest k-Tuple of Edge-Disjoint Paths

Shoji SHINODA  Shuji TSUKIYAMA  Isao SHIRAKAWA  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E70   No.10   pp.945-950
Publication Date: 1987/10/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
Let G be a directed graph containing n nodes and m edges, with each edge of nonnegative length. Given two specified nodes s and t, the length of a k-tuple of edge-disjoint paths from s to t in G is the sum of the lengths of all the edges on these k paths. A polynomial time algorithm for finding a shortest k-tuple of edge-disjoint paths from s to t in G has been devised. Based on this algorithm, this paper considers the problem of finding a second shortest k-tuple of edge-disjoint paths from s to t in G, for which an O (min[n3, nm log n])-time is described.