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.
An O (|E|)Hypercube Recognition Algorithm
Won-Ho CHUNG Cheol-Hoon LEE Doohun EUM
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1996/07/25
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
hypercube, n-cube, labeling,
Full Text: PDF>>
The n-dimensional hypercube is a highly concurrent loosely coupled multiprocessor based on the binary n-cube topology. This paper is concerned with the following basic graph-theoretic question: given a graph G = (V, E), is it an exact n-cube? We propose an O (|E|) hypercube recognition algorithm using some new topological properties of the hypercube graph.