For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Node-Disjoint Paths Problems in Directed Bijective Connection Graphs
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2020/01/01
Online ISSN: 1745-1361
Type of Manuscript: PAPER
Category: Fundamentals of Information Systems
multicomputer, interconnection network, parallel processing, hypercube, fault tolerance, performance evaluation,
Full Text: PDF(762.2KB)>>
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.