Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
PDF
  • On the maximal shortest paths cover number [Elektronski vir]
    Peterin, Iztok ; Semanišin, Gabriel
    Najkrajša pot ▫$P$▫ grafa ▫$G$▫ je najdaljša, če pot ▫$P$▫ ni vsebovana kot podpot katerekoli druge najkrajše poti. Množica ▫$S\subseteq V(G)$▫ je pokritje najdaljših najkrajših poti, če vsaka ... najdaljša najkrajša pot grafa ▫$G$▫ vsebuje kakšno vozlišče množice ▫$S$▫. Najmanjši moči pokritja najdaljših najkrajših poti rečemo število pokritja najdaljših najkrajših poti grafa ▫$G$▫ in ga označimo z ▫$\xi(G)$▫. Pokažemo, da je NP-težko določiti ▫$\xi(G)$▫. Predstavimo povezave med ▫$\xi(G)$▫ in nekaterimi drugimi parametri na grafih. Predstavimo linearen algoritem, ki določi natančno vrednost ▫$\xi(T)$▫ za vsako drevo ▫$T$▫.
    Vir: Mathematics [Elektronski vir]. - ISSN 2227-7390 (Vol. 9, iss. 14, July 2021, art. 1592 (10 str.))
    Vrsta gradiva - e-članek ; neleposlovje za odrasle
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 69766403

    Povezava(-e):

    https://www.mdpi.com/2227-7390/9/14/1592
    DOI

Vnos na polico