VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Algorithms for the edge-width of an embedded graph
    Cabello, Sergio ; Colin de Verdière, Éric, 1977- ; Lazarus, Francis
    Naj bo ▫$G$▫ neutežen graf kompleksnosti ▫$n$▫, ki je vložen v ploskev roda ▫$g$▫. Prikazan je izboljšani algoritem za določanje dolžine najkrajšega nestisljivega in najkrajšega neseparirajočega ... cikla v grafu. Za vsako naravno število ▫$k$▫ lahko najdemo tak cikel v času ▫$O(gnk)$▫, če je njegova dolžina kvečjemu ▫$k$▫. V nasprotnem primeru pa ugotovimo, da je dolžina večja od ▫$k$▫. Tako za poljubno izbrano ploskev lahko preverimo v linearnem času, če je povezavna ali celična širina vloženega grafa večja od ▫$k$▫. Prikazan je tudi aproksimacijski algoritem za iskanje najkrajšega netrivialnega cikla. Pri poljubnem danem parametru ▫$\varepsilon$▫ (▫$0< \varepsilon < 1$▫) dobimo v času ▫$O(gn/\varepsilon)$▫ netrivialni cikel, katerega dolžina je kvečjemu za faktor ▫$1+\varepsilon$▫ večja od najkrajšega takega cikla.
    Vir: 26th Annual Symposium on Computation Geometry at Snowbird, Utah, USA : Special issue (Str. 215-224)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2012
    Jezik - angleški
    COBISS.SI-ID - 16093017

    Povezava(-e):

    http://dx.doi.org/10.1016/j.comgeo.2011.12.002

Vnos na polico