VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Algorithms for graphs of bounded treewidth via orthogonal range searching
    Cabello, Sergio ; Knauer, Christian
    We show that, for any fixed constant ▫$k \ge 3$▫, the sum of the distances between all pairs of vertices of an abstract graphs with ▫$n$▫ vertices and treewidth at most ▫$k$▫ can be computed in ▫$O(n ... \log^{k-1}n)$▫ time. We also show that, for any fixed constant ▫$k \ge 2$▫, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with ▫$n$▫ vertices and treewidth at most ▫$k$▫ can be computed in ▫$O(n \log^{k+1} n)$▫ expected time. Recall that the dilation (or stretch-factor) of a geometric graph is the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance. The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth.
    Vir: Computational geometry. - ISSN 0925-7721 (Vol. 42, iss. 9, 2009, str. 815-824)
    Vrsta gradiva - e-članek
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15160409

    Povezava(-e):

    http://dx.doi.org/10.1016/j.comgeo.2009.02.001
    DOI

vir: Computational geometry. - ISSN 0925-7721 (Vol. 42, iss. 9, 2009, str. 815-824)
loading ...
loading ...
loading ...

Vnos na polico