VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Output-sensitive algorithm for the edge-width of an embedded graph
    Cabello, Sergio ; Colin de Verdière, Éric, 1977- ; Lazarus, Francis
    Let ▫$G$▫ be an unweighted graph of complexity ▫$n$▫ cellularly embedded in a surface (orientable or not) of genus ▫$g$▫. We describe improved algorithms to compute (the length of) a shortest ... non-contractible and a shortest non-separating cycle of ▫$G$▫. If ▫$k$▫ is an integer, we can compute such a non-trivial cycle with length at most ▫$k$▫ in ▫$O(gnk)$▫ time, or correctly report that no such cycle exists. In particular, on a fixed surface, we can test in linear time whether the edge-width or face-width of a graph is bounded from above by a constant. This also implies an output-sensitive algorithm to compute a shortest non-trivial cycle that runs in ▫$O(gnk)$▫ time, where ▫$k$▫ is the length of the cycle.
    Vir: Proceedings of the Twenty-Sixth Annual Symposium on Computational Geometry (SCG'10) : June 13-16, 2010, Snowbird, Utah, USA (Str. 147-155)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15629913

    Povezava(-e):

    http://doi.acm.org/10.1145/1810959.1810987

Vnos na polico