DIKUL - logo
(UL)
  • Computation of Grundy dominating sequences in (co-)bipartite graphs
    Brešar, Boštjan ; Pandey, Arti ; Sharma, Gopika
    Zaporedje ▫$S$▫ vozlišč grafa ▫$G$▫ se imenuje dominacijsko zaporedje grafa ▫$G$▫, če ▫$(i)$▫ vsako vozlišče ▫$v$▫ množice ▫$S$▫ dominira kako vozlišče grafa ▫$G$▫, ki še ni dominirano s strani ... predhodnih vozlišč v zaporedju in ▫$(ii)$▫ je vsako vozlišče grafa ▫$G$▫ dominirano s strani kakega vozlišča iz množice ▫$S$▫. Problem Grundyjeva dominacija išče najdaljše dominacijsko zaporedje danega grafa ▫$G$▫. Znano je, da je odločitvena verzija problema Grundyjeva dominacija NP-poln problem, celo če se omejimo na tetivne grafe. V tem članku dokažemo, da je odločitvena verzija problema Grundyjeva dominacija NP-problem v dvodelnih grafih in tudi v njihovih komplementih, ko-dvodelnih grafih. Po drugi strani nam uspe konstruirati linearen algoritem, ki reši problem Grundyjeva dominacija v verižnih grafih, ki tvorijo podrazred dvodelnih grafov.
    Source: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, iss. 8, [article no.] 359, Dec. 2023, 17 str.)
    Type of material - article, component part ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 173382915

    Link(s):

    https://link.springer.com/article/10.1007/s40314-023-02500-w
    DOI

source: Computational & Applied Mathematics. - ISSN 2238-3603 (Vol. 42, iss. 8, [article no.] 359, Dec. 2023, 17 str.)

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

Shelf entry