No Access

A SOLUTION TO THE THREE DISJOINT PATH PROBLEM ON HONEYCOMB MESHES

XIAOFAN YANG

Department of Computer Science, Chongqing University, Chongqing, 430044, China

Search for more papers by this author

GRAHAM M. MEGSON

Department of Computer Science, University of Reading, P O Box 225, Whiteknights, Reading, Berkshire, RG6 6AY, UK

Search for more papers by this author

SHAOMlN ZHANG

Department of Computer Science, Shenyang Institute of Technology, Shenyang, China

Search for more papers by this author

, and

XIAOPING LIU

Institute of Multimedia Network and Telecommunication Engineering, Wuhan Technological University of Surveying and Mapping, Wuhan, 430079, China

Search for more papers by this author

https://doi.org/10.1142/S0129626404001982Cited by:7 (Source: Crossref)

Abstract

Recently honeycomb meshes have been considered as alternative candidates for interconnection networks in parallel and distributed computer systems. This paper presents a solution to one of the open problems about honeycomb meshes—the so-called three disjoint path problem. The problem requires minimizing the length of the longest of any three disjoint paths between 3-degree nodes. This solution provides information on the re-routing of traffic along the network in the presence of faults.

This work is partly supported by Chinese National Natural Science Research Funds and Chinese National Education Committee Overseas Scholar Research Funds (Grant Number 96851032)

Keywords:

References

V. Kumar et al. , Introducing to Parallel Computing: Design and Analysis of Algorithms ( The Benjamin/Cummings Publishing Company, Inc. , 1994 ) . Google Scholar
S. G. Akl , The Design and Analysis of Parallel Algorithms ( Prentice-Hall International, Inc. , 1989 ) . Google Scholar
D. Milutinovic, V. Milutinovic and B. Soucek, Computer 20(4), 81 (1987). Crossref, Web of Science, Google Scholar
V. Milutinovic, Proc. IEEE 77(12), 1875 (1989). Crossref, Web of Science, Google Scholar
I. Stojmenovic, IEEE Trans. Parallel & Distributed Systems 8(10), 1036 (1997). Crossref, Web of Science, Google Scholar