Patent ID: 6038688
Filing Date: 2000-03-14
Classification: G06F

Abstract:
A method for searching a node disjoint path by avoiding a damaged node existing in an n-dimensional hyper cube, comprising:a first step for forming a linear arrangement consisting of an n-number of integers (0, 1, 2, . . . n-1) with respect to an n-dimension and searching a linear arrangement which is not neighbored in a linear arrangement in which integers which indicate a value of 1 in an address of a damaged node are circulated, assuming that a node address with respect to an n-address is expressed as a position of 1 among an n-number of binary digits, separating each value by a comma by defining an address value of a decimal digit indicating a position of 1 using a bracket, defining the rightmost position as 0 and the leftmost position as n-1; anda second step for forming a linear arrangement using integers of an arrangement in which values indicating a position of 1 in an address of a damaged node are not neighbored on a circumferential portion, moving the linear arrangement by one digit in the right direction and forming an n.times.n first matrix, as follows: ##STR3## where, n denotes positive integers wherein the integer indicating the damaged node address is not neighbored each other in an arrangement of ""0,1, . . . , (n-1)"" of a first row and column:wherein an n.times.n second matrix indicating a node address with respect to an n-dimension by forming a linear arrangement with respect to a first matrix, as follows: ##STR4## whereby a step for generating a node of an address which is expressed in a linear arrangement of each row as a node disjoint path is performed.