For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On a Second Shortest k-Tuple of Edge-Disjoint Paths
Shoji SHINODA Shuji TSUKIYAMA Isao SHIRAKAWA
IEICE TRANSACTIONS (1976-1990)
Publication Date: 1987/10/25
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Graphs and Networks
Full Text: PDF>>
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.