The Tower of Hanoi problem on Path_h graphs

Details The Tower of Hanoi problem on Path_h graphs The Tower of Hanoi problem on Path_h graphs

2011-02-24

arxiv.org/abs/1102.4885v1

Computer Science

Discrete Mathematics

32 pages, 2 figures

Scientific paper

The generalized Tower of Hanoi problem with h \ge 4 pegs is known to require a sub-exponentially 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(h-1)/2 possible bi-directional interconnections among pegs, here there are only h-1 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 sub-exponentially 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.

Affiliated with

Also associated with

No associations

Rating

The Tower of Hanoi problem on Path_h graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Tower of Hanoi problem on Path_h graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Tower of Hanoi problem on Path_h graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-86070