VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Hitting subgraphs in ▫$P_4$▫-tidy graphs
    Brešar, Boštjan ...
    Število vozliščnega pokritja, ki je ena najbolj osnovnih invariant grafov, lahko razumemo kot najmanjše število vozlišč, ki zadenejo vsak podgraf ▫$K_2$▫ v grafu ▫$G$▫. V tem članku obravnavamo dva ... naslednja najmanjša primera povezanih grafov, ki sta pot ▫$P_3$▫ in cikel ▫$C_3$▫; problem je minimizirati množico vozlišč, ki zadenejo vsak podgraf ▫$H$▫ grafa ▫$G$▫, kjer je ▫$H$▫ eden od obeh grafov. Osredotočimo se na računske vidike teh dveh variacij števila vozliščnega pokritja. Dokažemo, da sta oba problema NP-polna celo v razredu grafov, ki nimajo induciranih ciklov dolžine ▫$t$▫, kjer je ▫$t\in\{4,\ldots, 8\}$▫ (v primeru grafa ▫$P_3$▫ je problem NP-poln celo v manjši družini grafov, kjer so prepovedani tudi trikotniki). Na pozitivni strani pa dokažemo komplementaren rezultat, ki pravi, da v grafih, ki nimajo induciranih ▫$P_4$▫ (takim grafov pravimo tudi kografi) oba problema postaneta linearna. Še več, obravnavamo tudi posplošitev kografov -- ▫$P_4$▫-urejene grafe, za katere predstavimo učinkovit algoritem za oba problema.
    Vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 352, July 2019, str. 211-219)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2019
    Jezik - angleški
    COBISS.SI-ID - 18568025

    Povezava(-e):

    https://doi.org/10.1016/j.amc.2019.01.074
    DOI

Vnos na polico