VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Efficient polynomial-time approximation scheme for the genus of dense graphs [Elektronski vir]
    Jing, Yifan ; Mohar, Bojan, 1956-
    The results of this paper provide an Efficient Polynomial-Time Approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. The running time of the algorithm ... is quadratic. Moreover, we extend the algorithm to output an embedding (rotation system), whose genus is arbitrarily close to the minimum genus. This second algorithm is an Efficient Polynomial-time Randomized Approximation Scheme (EPRAS) and the expected running time is also quadratic.
    Vir: 59th Annual IEEE Symposium on Foundations of Computer Science [Elektronski vir] : FOCS 2018 : proceedings : 7-9 October 2018, Paris, France (Str. 719-730)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2018
    Jezik - angleški
    COBISS.SI-ID - 18855001

    Povezava(-e):

    https://doi.org/10.1109/FOCS.2018.00074
    DOI

Vnos na polico