
Computer Science 2011
The Tower of Hanoi problem on Path_h graphsAbstract: The generalized Tower of Hanoi problem with h \ge 4 pegs is known to require a subexponentially fast growing number of moves in order to transfer a pile of n disks from one peg to another. In this paper we study the Path_h variant, where the pegs are placed along a line, and disks can be moved from a peg to its nearest neighbor(s) only. Whereas in the simple variant there are h(h1)/2 possible bidirectional interconnections among pegs, here there are only h1 of them. Despite the significant reduction in the number of interconnections, the number of moves needed to transfer a pile of n disks between any two pegs also grows subexponentially as a function of n. We study these graphs, identify sets of mutually recursive tasks, and obtain a relatively tight upper bound for the number of moves, depending on h, n and the source and destination pegs.
