[[alternative]]On Finding a Ring in an Injured Hypercube Using the Incomplete Hypercube Model

[[abstract]]It is well known that the general problem of finding a Hamilton cycle (ring) in an arbitary graph is NP - complete. However, in an - dimensional hypercube, an advocated symmetric topological structure, the searching of a Hamilton cycle (ring) can be easily carried out in O (N), where N is the number of nodes in a complete hypercube. In an injured hypercube which has faulty nodes, the above O (N) algorithrn can't be applied for finding a ring in it. Hence, the purpose of our research is to develop a heuristic algorithm to find rings in the injured hypercubes. In this thesis, we develop a new incomplete hypercube model, which uses a subcbe - graph to present the topology of an injured hypercube, to provide a better representation for it. This incomplete hypercube model server as the foundation for our ring embeding algorithm. Our ring embedding algorthm employs depth - first search on subcube - graph associated with a heuristic break edge method to derive a ring passing through the maximal possible number of the available processor elements in the injured hypercube. Our method can provide a ring embedding on an injured hypercube with high processor utilization. Also, our method has no limitation on the number of faulty nodes that bothers many existing fault - tolerant ring embedding schemes. The time complexity of our method is O (mn), where m is the number of cube - nodes in a subcube - graph and n is the dimension of the injured hypercube.