DIKUL - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • Algorithms for the edge-width of an embedded graph [Elektronski vir]
    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. We also give an approximation algorithm for the shortest non-trivial cycle. If a parameter ▫$0 < \varepsilon < 1$▫ is given, we compute in ▫$O(gn/\varepsilon)$▫ time a non-trivial cycle whose length is at most ▫$1 + \varepsilon$▫ times the length of the shortest non-trivial cycle.
    Vir: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 48, št. 1125, 2010, str. 1-16)
    Vrsta gradiva - e-članek
    Leto - 2010
    Jezik - angleški
    COBISS.SI-ID - 15638617

    Povezava(-e):

    http://www.imfm.si/preprinti/PDF/01125.pdf

Vnos na polico