IEICE TRANSACTIONS on transactions
On a Second Shortest k-Tuple of Edge-Disjoint Paths
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.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E70-E No.10 pp.945-950
- Publication Date
- 1987/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shoji SHINODA, Shuji TSUKIYAMA, Isao SHIRAKAWA, "On a Second Shortest k-Tuple of Edge-Disjoint Paths" in IEICE TRANSACTIONS on transactions,
vol. E70-E, no. 10, pp. 945-950, October 1987, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e70-e_10_945/_p
Copy
@ARTICLE{e70-e_10_945,
author={Shoji SHINODA, Shuji TSUKIYAMA, Isao SHIRAKAWA, },
journal={IEICE TRANSACTIONS on transactions},
title={On a Second Shortest k-Tuple of Edge-Disjoint Paths},
year={1987},
volume={E70-E},
number={10},
pages={945-950},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - On a Second Shortest k-Tuple of Edge-Disjoint Paths
T2 - IEICE TRANSACTIONS on transactions
SP - 945
EP - 950
AU - Shoji SHINODA
AU - Shuji TSUKIYAMA
AU - Isao SHIRAKAWA
PY - 1987
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E70-E
IS - 10
JA - IEICE TRANSACTIONS on transactions
Y1 - October 1987
AB - 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.
ER -
English
