Node-Disjoint Paths Problems in Directed Bijective Connection Graphs

Keiichi KANEKO  

IEICE TRANSACTIONS on Information and Systems   Vol.E103-D   No.1   pp.93-100
Publication Date: 2020/01/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2019EDP7197
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
multicomputer,  interconnection network,  parallel processing,  hypercube,  fault tolerance,  performance evaluation,  

Full Text: PDF(762.2KB)>>
Buy this Article

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.