Akademska digitalna zbirka SLovenije - logo
(UL)
PDF
  • The geodesic-transversal problem
    Manuel, Paul ; Brešar, Boštjan ; Klavžar, Sandi
    Maksimalna geodetka (oz. najkrajša pot) v grafu je geodetka, ki ni vsebovana v nobeni daljši geodetki. V članku uvedemo geodetski transverzalni problem grafa $G$ kot nalogo poiskati najmanjšo tako ... množico $S$ vozlišč grafa $G$, da vsaka maksimalna geodetka vsebuje vsaj eno vozlišče iz $S$. Najmanjša moč takšne množice se imenuje geodetsko transverzalno število grafa $G$ in se označi z ${\rm gt}(G)$. Dokažemo, da je ${\rm gt}(G)=1$ natanko tedaj, ko je $G$ subdividirana zvezda in da geodetsko transverzalno število poraja NP-poln problem. Izdelamo hitra algoritma za določitev geodetskega transverzalnega števila dreves ter razpredenih kaktusov.
    Vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 413, Jan. 2022, art. 126621 (11 str.))
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2022
    Jezik - angleški
    COBISS.SI-ID - 76871939

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0096300321007050
    DOI

vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 413, Jan. 2022, art. 126621 (11 str.))

loading ...
loading ...
loading ...

Vnos na polico