Constant Time Algorithms in Maze Routing

N. Nagy (Canada)

Keywords

Abstract

Maze routing is largely used in VLSI design. Lee designed efficient sequential algorithms, with 0(N²) 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 12N⁴ processors and 4N⁴ busses.

Important Links:

• DOI:
• From Proceeding (373) Parallel and Distributed Computing and Systems - 2002

Go Back