An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs
Summary :
An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).
- Publication
- IEICE TRANSACTIONS on Information Vol.E89-D No.2 pp.647-653
- Publication Date
- 2006/02/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e89-d.2.647
- Type of Manuscript
- Special Section PAPER (Special Section on Parallel/Distributed Computing and Networking)
- Category
- Parallel/Distributed Algorithms
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, "An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs" in IEICE TRANSACTIONS on Information,
vol. E89-D, no. 2, pp. 647-653, February 2006, doi: 10.1093/ietisy/e89-d.2.647.
Abstract: An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e89-d.2.647/_p
Copy
@ARTICLE{e89-d_2_647,
author={Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs},
year={2006},
volume={E89-D},
number={2},
pages={647-653},
abstract={An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).},
keywords={},
doi={10.1093/ietisy/e89-d.2.647},
ISSN={1745-1361},
month={February},}
Copy
TY - JOUR
TI - An Algorithm for Node-to-Set Disjoint Paths Problem in Bi-Rotator Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 647
EP - 653
AU - Keiichi KANEKO
PY - 2006
DO - 10.1093/ietisy/e89-d.2.647
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E89-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2006
AB - An algorithm is described for solving the node-to-set disjoint paths problem in bi-rotator graphs, which are obtained by making each edge of a rotator graph bi-directional. The algorithm is of polynomial order of n for an n-bi-rotator graph. It is based on recursion and divided into three cases according to the distribution of destination nodes in the classes into which the nodes in a bi-rotator graph are categorized. We estimated that it obtains 2n-3 disjoint paths with a time complexity of O(n5), that the sum of the path lengths is O(n3), and that the length of the maximum path is O(n2). Computer experiment showed that the average execution time was O(n3.9) and, the average sum of the path lengths was O(n3.0).
ER -
English
