ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • 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.
    Source: 26th Annual Symposium on Computation Geometry at Snowbird, Utah, USA : Special issue (Str. 215-224)
    Type of material - conference contribution
    Publish date - 2012
    Language - english
    COBISS.SI-ID - 16093017

    Link(s):

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

Shelf entry