Internally-Disjoint Paths Problem in Bi-Rotator Graphs
Summary :
A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.
- Publication
- IEICE TRANSACTIONS on Information Vol.E88-D No.7 pp.1678-1684
- Publication Date
- 2005/07/01
- Publicized
- Online ISSN
- DOI
- 10.1093/ietisy/e88-d.7.1678
- Type of Manuscript
- PAPER
- Category
- Dependable Computing
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
Keiichi KANEKO, "Internally-Disjoint Paths Problem in Bi-Rotator Graphs" in IEICE TRANSACTIONS on Information,
vol. E88-D, no. 7, pp. 1678-1684, July 2005, doi: 10.1093/ietisy/e88-d.7.1678.
Abstract: A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.7.1678/_p
Copy
@ARTICLE{e88-d_7_1678,
author={Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Internally-Disjoint Paths Problem in Bi-Rotator Graphs},
year={2005},
volume={E88-D},
number={7},
pages={1678-1684},
abstract={A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.},
keywords={},
doi={10.1093/ietisy/e88-d.7.1678},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - Internally-Disjoint Paths Problem in Bi-Rotator Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 1678
EP - 1684
AU - Keiichi KANEKO
PY - 2005
DO - 10.1093/ietisy/e88-d.7.1678
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 7
JA - IEICE TRANSACTIONS on Information
Y1 - July 2005
AB - A rotator graph was proposed as a topology for interconnection networks of parallel computers, and it is promising because of its small diameter and small degree. However, a rotator graph is a directed graph that sometimes behaves harmfully when it is applied to actual problems. A bi-rotator graph is obtained by making each edge of a rotator graph bi-directional. In a bi-rotator graph, average distance is improved against a rotator graph with the same number of nodes. In this paper, we give an algorithm for the container problem in bi-rotator graphs with its evaluation results. The solution achieves some fault tolerance such as file distribution based information dispersal technique. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into two cases according to the position of the destination node. The time complexity of the algorithm and the maximum length of paths obtained are estimated to be O(n3) and 4n-5, respectively. Average performance of the algorithm is also evaluated by computer experiments.
ER -
English
