VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Computational complexity aspects of super domination
    Bujtás, Csilla ; Ghanbari, Nima ; Klavžar, Sandi
    Naj bo ▫$G$▫ graf. Dominantna množica ▫$D\subseteq V(G)$▫ je super dominantna množica, če za vsako vozlišče ▫$x\in V(G) \setminus D$▫ obstaja ▫$y\in D$▫ tako, da je ▫$N_G(y)\cap (V(G)\setminus D)) = ... \{x\}$▫. Kardinalnost najmanjše super dominantne množice ▫$G$▫ je število super dominacije ▫$G$▫. Pridobljena je natančna formula za super dominacijsko število drevesa ▫$T$▫ in dokazano je, da je najmanjšo super dominantno množico ▫$T$▫ mogoče izračunati v linearnem času. Dokazano je, da je NP-polno odločiti, ali je število super dominacije grafa ▫$G$▫ kvečjemu določeno celo število, če je ▫$G$▫ dvodelen graf z ožino vsaj ▫$8$▫. Število super dominacije je določeno za vse ▫$k$▫-subdivizije grafov. Zanimivo je, da lahko v polovici primerov natančno vrednost učinkovito izračunamo iz dobljenih formul, v drugih primerih pa je izračun težaven. Pri pridobivanju teh formul so uvedena števila II-prirejanja in dokazano je, da jih je računsko težko določiti.
    Vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 975, art. no. 114137, Oct. 2023, 14 str.)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 162318851

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0304397523004504
    DiRROS - Digitalni repozitorij raziskovalnih organizacij Slovenije
    Repozitorij Univerze v Ljubljani – RUL
    DOI

vir: Theoretical computer science. - ISSN 0304-3975 (Vol. 975, art. no. 114137, Oct. 2023, 14 str.)
loading ...
loading ...
loading ...

Vnos na polico