Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • An efficient algorithm to determine all shortest paths in Sierpiński graphs
    Hinz, Andreas M. ; Holz auf der Heide, Caroline
    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.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 177, 2014, str. 111-120)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2014
    Jezik - angleški
    COBISS.SI-ID - 17183833

    Povezava(-e):

    http://dx.doi.org/10.1016/j.dam.2014.05.049

vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 177, 2014, str. 111-120)

loading ...
loading ...
loading ...

Vnos na polico