DIKUL - logo
(UL)
  • 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.
    Source: Theoretical computer science. - ISSN 0304-3975 (Vol. 975, art. no. 114137, Oct. 2023, 14 str.)
    Type of material - article, component part ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 162318851

    Link(s):

    https://www.sciencedirect.com/science/article/pii/S0304397523004504
    DiRROS - Digital repository of Slovenian research organizations
    Repository of the University of Ljubljana – RUL
    DOI

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

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

Shelf entry