DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Multiple source shortest paths in a genus g graph
    Cabello, Sergio ; Chambers, Erin W.
    We give an ▫$O(g^2n \log n)$▫ algorithm to represent the shortest path tree from all the vertices on a single specified face ▫$f$▫ in a genus $g$ graph. From this representation, any query distance ... from a vertex in ▫$f$▫ can be obtained in ▫$O(\log n)$▫ time. The algorithm uses a kinetic data structure, where the source of the tree iteratively moves across edges in ▫$f$▫. In addition, we give applications using these shortest path trees in order to compute the shortest non-contractible cycle and the shortest non-separating cycle embedded on an orientable 2-manifold in ▫$O(g^3 n \log n)$▫ time.
    Vir: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Str. 89-97)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 14229337

Vnos na polico