PARALLELISM FOR MULTIPEG TOWERS-OF-HANOI

This paper studies parallelism for the multipeg Towers of Hanoi proble m, an interesting generalization of the traditional one, by allowing c oncurrent moves of discs in a single step. Three versions of paralleli sm are investigated based on two factors: the order of moves of discs and the resource utilization of pegs. Solutions obtained include the m inimum numbers of steps and algorithms for moving discs in the minimum numbers of steps. A common technique is presented for deriving the no nrecursive computation of minimum numbers of steps, which discloses a methodology for the study of parallelism in the multipeg Towers.