IEICE TRANSACTIONS on Information
Node-Disjoint Paths Problems in Directed Bijective Connection Graphs
Summary :
In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.
- Publication
- IEICE TRANSACTIONS on Information Vol.E103-D No.1 pp.93-100
- Publication Date
- 2020/01/01
- Publicized
- 2019/09/26
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.2019EDP7197
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Keiichi KANEKO
Tokyo University of Agriculture and Technology
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, "Node-Disjoint Paths Problems in Directed Bijective Connection Graphs" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 1, pp. 93-100, January 2020, doi: 10.1587/transinf.2019EDP7197.
Abstract: In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2019EDP7197/_p
Copy
@ARTICLE{e103-d_1_93,
author={Keiichi KANEKO, },
journal={IEICE TRANSACTIONS on Information},
title={Node-Disjoint Paths Problems in Directed Bijective Connection Graphs},
year={2020},
volume={E103-D},
number={1},
pages={93-100},
abstract={In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.},
keywords={},
doi={10.1587/transinf.2019EDP7197},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - Node-Disjoint Paths Problems in Directed Bijective Connection Graphs
T2 - IEICE TRANSACTIONS on Information
SP - 93
EP - 100
AU - Keiichi KANEKO
PY - 2020
DO - 10.1587/transinf.2019EDP7197
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2020
AB - In this paper, we extend the notion of bijective connection graphs to introduce directed bijective connection graphs. We propose algorithms that solve the node-to-set node-disjoint paths problem and the node-to-node node-disjoint paths problem in a directed bijective connection graph. The time complexities of the algorithms are both O(n4), and the maximum path lengths are both 2n-1.
ER -
English
