Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Multiple-source shortest paths in embedded graphs
    Cabello, Sergio ; Chambers, Erin W. ; Erickson, Jeff
    Let ▫$G$▫ be a directed graph with ▫$n$▫ vertices and nonnegative weights in its directed edges, embedded on a surface of genus ▫$g$▫, and let ▫$f$▫ be an arbitrary face of ▫$G$▫. We describe a ... randomized algorithm to preprocess the graph in ▫$O(gn \log n)$▫ time with high probability, so that the shortest-path distance from any vertex on the boundary of ▫$f$▫ to any other vertex in ▫$G$▫ canbe retrieved in ▫$O(\log n)$▫ time. Our result directly generalizes the ▫$O(n\log n)$▫-time algorithm of Klein [Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005] for multiple-source shortest paths in planar graphs. Intuitively, our preprocessing algorithm maintains a shortest-path tree as its source point moves continuously around the boundary of ▫$f$▫. As an application of our algorithm, we describe algorithms to compute a shortest noncontractible or nonseparating cycle in embedded, undirected graphs in ▫$O(g^2 n\log n)$▫ time with high probability. Our high-probability time bounds hold in the worst case for generic edge weights or with an additional ▫$O(\log n)$▫ factor for arbitrary edge weights.
    Vir: SIAM journal on computing. - ISSN 0097-5397 (Vol. 42, no. 4, 2013, str. 1542-1571)
    Vrsta gradiva - članek, sestavni del
    Leto - 2013
    Jezik - angleški
    COBISS.SI-ID - 16668761

    Povezava(-e):

    http://dx.doi.org/10.1137/120864271

vir: SIAM journal on computing. - ISSN 0097-5397 (Vol. 42, no. 4, 2013, str. 1542-1571)
loading ...
loading ...
loading ...

Vnos na polico