Hinz, Andreas M.; Holz auf der Heide, Caroline An efficient algorithm to determine all shortest paths in Sierpiński graphs. (English) Zbl 1300.05147 Discrete Appl. Math. 177, 111-120 (2014). Summary: In the switching tower of Hanoi interpretation of Sierpiński graphs \(S_p^n\), 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=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 \(n\). Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented. Cited in 21 Documents MSC: 05C38 Paths and cycles 05C12 Distance in graphs 05C35 Extremal problems in graph theory Keywords:shortest path algorithm; automata; Sierpiński graphs; switching tower of Hanoi PDFBibTeX XMLCite \textit{A. M. Hinz} and \textit{C. Holz auf der Heide}, Discrete Appl. Math. 177, 111--120 (2014; Zbl 1300.05147) Full Text: DOI References: [2] Cristea, L. L.; Steinsky, B., Distances in Sierpiński graphs and on the Sierpiński gasket, Aequationes Math., 85, 201-219 (2013) · Zbl 1275.28007 [3] Hinz, A. M., The Tower of Hanoi, Enseign. Math. (2), 35, 289-321 (1989) · Zbl 0746.05035 [4] Hinz, A. M., Shortest paths between regular states of the Tower of Hanoi, Inform. Sci., 63, 173-181 (1992) · Zbl 0792.68125 [5] Hinz, A. M.; Klavžar, S.; Milutinović, U.; Parisse, D.; Petr, C., Metric properties of the Tower of Hanoi graphs and Stern’s diatomic sequence, European J. Combin., 26, 693-708 (2005) · Zbl 1060.05007 [6] Hinz, A. M.; Klavžar, S.; Milutinović, U.; Petr, C., The Tower of Hanoi—Myths and Maths (2013), Springer: Springer Basel · Zbl 1285.00003 [7] Hinz, A. M.; Parisse, D., The average eccentricity of Sierpiński graphs, Graphs Combin., 28, 671-686 (2012) · Zbl 1256.05058 [8] Klavžar, S.; Milutinović, U., Graphs \(S(n, k)\) and a variant of the Tower of Hanoi problem, Czechoslovak Math. J., 47, 122, 95-104 (1997) · Zbl 0898.05042 [9] Klavžar, S.; Peterin, I.; Zemljič, S. S., Hamming dimension of a graph—The case of Sierpiński graphs, European J. Combin., 34, 460-473 (2013) · Zbl 1254.05046 [10] Klavžar, S.; Zemljič, S. S., On distances in Sierpiński graphs: almost-extreme vertices and metric dimension, Appl. Anal. Discrete Math., 7, 72-82 (2013) · Zbl 1408.05050 [11] Parisse, D., The Tower of Hanoi and the Stern-Brocot Array (1997), Ludwig-Maximilians-Universität: Ludwig-Maximilians-Universität München, (Ph.D. thesis) · Zbl 0897.11005 [12] Parisse, D., On some metric properties of the Sierpiński graphs \(S(n, k)\), Ars Combin., 90, 145-160 (2009) · Zbl 1224.05153 [13] Romik, D., Shortest paths in the Tower of Hanoi graph and finite automata, SIAM J. Discrete Math., 20, 610-622 (2006) · Zbl 1127.68069 [14] Wiesenberger, H.-L., Stochastische Eigenschaften von Hanoi- und Sierpiński-Graphen (2010), Ludwig-Maximilians-Universität: Ludwig-Maximilians-Universität München, (Diploma thesis) [15] Xue, B.; Zuo, L.; Wang, G.; Li, G., Shortest paths in Sierpiński graphs, Discrete Appl. Math., 162, 314-321 (2014) · Zbl 1297.05123 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.