کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418293 | 681627 | 2014 | 10 صفحه PDF | دانلود رایگان |
In the Switching Tower of Hanoi interpretation of Sierpiński graphs Spn, the P2 decision problem is to find out whether the largest moving disc has to be transferred once or twice in a shortest path between two given states/vertices. We construct an essentially optimal algorithm thus extending Romik’s approach for p=3p=3 to the general case. The algorithm makes use of three automata and the underlying theory includes a simple argument for the fact that there are at most two shortest paths between any two vertices. The total number of pairs leading to non-unique solutions is determined and employing a Markov chain argument it is shown that the number of input pairs needed for the decision is bounded above by a number independent of nn. Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented.
Journal: Discrete Applied Mathematics - Volume 177, 20 November 2014, Pages 111–120