An O (|E|)Hypercube Recognition Algorithm

Won-Ho CHUNG  Cheol-Hoon LEE  Doohun EUM  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.7   pp.994-996
Publication Date: 1996/07/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
hypercube,  n-cube,  labeling,  

Full Text: PDF>>
Buy this Article

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.