Constant Time Algorithms in Maze Routing

N. Nagy (Canada)



Maze routing is largely used in VLSI design. Lee designed efficient sequential algorithms, with 0(N2) complexity to solve the maze routing problem, on an N × N maze. Ercal and Lee proposed constant time parallel algorithms to find particular paths in a maze. This paper solves the maze routing problem in the general case. The algorithm takes constant time and runs on a Reconfigurable Mutliple Bus Machine (RMBM) with 12N4 processors and 4N4 busses.

Important Links:

Go Back