Akademska digitalna zbirka SLovenije - logo
(UL)
  • A planar linear arboricity conjecture [Elektronski vir]
    Cygan, Marek ; Kowalik, Łukasz ; Lužar, Borut
    Linearna razvejanost ▫${\rm la}(G)$▫ grafa ▫$G$▫ je najmanjše število linearnih gozdov (grafov, v katerih je vsaka povezana komponenta pot), ki delijo povezave ▫$G$▫. Leta 1984 so Akiyama et al. ... podali hipotezo o linearni razvejanosti (Linear Arboricity Conjecture (LAC)), ki pravi, da je linearna razvejanost poljubnega enostavnega grafa z maksimalno stopnjo ▫$\Delta$▫ ali ▫$\big \lceil \tfrac{\Delta}{2} \big \rceil$ ali $\big \lceil \tfrac{\Delta+1}{2} \big \rceil$▫. Dokazano je že, da LAC drži za vse ravninske grafe. Iz LAC sledi, da za lihe ▫$\Delta$▫ velja ▫${\rm la}(G)=\big \lceil \tfrac{\Delta}{2} \big \rceil$▫. V članku postavimo hipotezo, ki pravi, da je zgornja enakost resnična tudi za vse sode ▫$\Delta \ge 6$▫. Dokazali smo, da drži za vse sode ▫$\Delta \ge 10$▫. Odprto ostane vprašanje za ▫$\Delta=6, 8$▫. Predstavimo tudi algoritem s časovno zahtevnostjo ▫$O(n\log n)$▫, ki razdeli ravninski graf na ▫$\max\{{\rm la}(G), 5\}$▫ linearnih gozdov, ki je optimalen za ▫$\Delta \ge 9$▫.
    Source: Preprint series [Elektronski vir]. - ISSN 2232-2094 (Vol. 48, št. 1111, 2010, str. 1-22)
    Type of material - e-article
    Publish date - 2010
    Language - english
    COBISS.SI-ID - 15437401

    Link(s):

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

Shelf entry