Finding hamiltonian cycles on incrementally extensible hypercube graphs

機構典藏 > College of Engineering > Graduate Institute & Department of Computer Science and Information Engineering > Proceeding > Item 987654321/37678

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/37678

Title:	Finding hamiltonian cycles on incrementally extensible hypercube graphs
Authors:	Keh, Huan-chao;Chou, Po-yu;Lin, Jen-chih
Contributors:	淡江大學資訊工程學系
Date:	1997-04-28
Issue Date:	2010-01-11 13:56:11 (UTC+8)
Abstract:	The existence of a Hamiltonian cycle is the premise of usage in an interconnection network. A novel interconnection network, the incrementally extensible hypercube (IEH) graph, has been proposed. The IEH graphs are derived from hypercubes and also retain most of the properties of hypercubes. Unlike hypercubes without incremental extensibility, IEH graphs can be constructed in any number of nodes. In this paper, we present an algorithm to find a Hamiltonian cycle or path and prove that there exists a Hamiltonian cycle in all IEH graphs except for those containing exactly 2<sup>n</sup>-1 nodes.
Relation:	Proceedings of high performance computing on the information superhighway. HPC Asia 97 Conference and Exhibition, pp.361-366
DOI:	10.1109/HPC.1997.592174
Appears in Collections:	[Graduate Institute & Department of Computer Science and Information Engineering] Proceeding

Files in This Item:

File	Description	Size	Format
Finding Hamiltonian Cycles on Incrementally Extensible Hypercube.pdf		524Kb	Adobe PDF	402	View/Open
index.html		0Kb	HTML	290	View/Open