ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • Variety of mutual-visibility problems in graphs
    Cicerone, Serafino ...
    Če je ▫$X$▫ podmnožica vozlišč grafa ▫$G$▫, potem sta vozlišči ▫$u$▫ in ▫$v$▫ ▫$X$▫-vidni, če obstaja najkrajša ▫$u,v$▫ pot ▫$P$▫, tako da velja ▫$V(P)\cap X \subseteq \{u,v\}$▫. Če sta vsaki dve ... vozlišči ▫$X$▫-vidni, potem je ▫$X$▫ množica vzajemne vidnosti. Število vzajemne vidnosti ▫$G$▫ je kardinalnost največje množice vzajemne vidnosti ▫$G$▫ in je bilo že raziskano. V tem članku so predstavljeni različni problemi vzajemne vidnosti, ki temeljijo na tem, kateri naravni pari vozlišč morajo biti ▫$X$▫-vidni. Tako dobimo število celotne, dualne in zunanje vzajemne vidnosti. Najprej pokažemo, da so te grafne invariante povezane med seboj in s klasičnim številom vzajemne vidnosti, nato pa dokažemo, da so trije na novo uvedeni problemi vzajemne vidnosti računsko zahtevni. V skladu s tem rezultatom izračunamo ali omejimo njihove vrednosti za več razredov grafov, ki vključujejo na primer mrežne grafe in torusne grafe. Članek zaključimo s predstavitvijo nekaterih medsebojnih primerjav vrednosti teh parametrov, ki temeljijo na izračunih, ki smo jih opravili za nekatere specifične družine.
    Source: Theoretical computer science. - ISSN 0304-3975 (Vol. 974, art. no. 114096, Sep. 2023, 13 str.)
    Type of material - article, component part ; adult, serious
    Publish date - 2023
    Language - english
    COBISS.SI-ID - 161787907

    Link(s):

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

source: Theoretical computer science. - ISSN 0304-3975 (Vol. 974, art. no. 114096, Sep. 2023, 13 str.)
loading ...
loading ...
loading ...

Shelf entry