Routing Problems in Incomplete Pancake Graphs

Author

Kaneko, Keiichi

Author_Institution

Inst. of Symbiotic Sci. & Technol., Tokyo Univ. of Agric. & Technol.

fYear

2006

fDate

19-20 June 2006

Firstpage

151

Lastpage

156

Abstract

A pancake graph was proposed as a topology for interconnection networks of parallel computers, and it has a merit that it can connect many nodes with small diameter and small degree. However, the number of nodes in a pancake graph must be equal to the factorial of an integer, which causes a demerit that it lacks incremental expandability. Hence, in this paper, we propose a graph, an incomplete pancake graph, that is obtained by deleting some of sub graphs of a pancake graph, and we give algorithms for the problems of the simple routing, the Hamiltonian cycle, the Hamiltonian path, and the container in incomplete pancake graphs

Keywords

computer networks; parallel processing; telecommunication network routing; Hamiltonian cycle; Hamiltonian path; incomplete pancake graphs; interconnection network topology; parallel computers; routing problems; Agriculture; Computer networks; Concurrent computing; Containers; Distributed computing; Intelligent networks; Multiprocessor interconnection networks; Network topology; Routing; Symbiosis;

fLanguage

English

Publisher

ieee

Conference_Titel

Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, 2006. SNPD 2006. Seventh ACIS International Conference on

Conference_Location

Las Vegas, NV

Print_ISBN

0-7695-2611-X

Type

conf

DOI

10.1109/SNPD-SAWN.2006.61

Filename

1640682