×

An efficient algorithm to determine all shortest paths in Sierpiński graphs. (English) Zbl 1300.05147

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.

MSC:

05C38 Paths and cycles
05C12 Distance in graphs
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
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.