ALL libraries (COBIB.SI union bibliographic/catalogue database)
  • The recognition problem of graph search trees
    Beisegel, Jesse ...
    Iskanje po grafih in ustrezna iskalna drevesa lahko kažejo pomembne strukturne lastnosti in se uporabljajo v različnih grafovskih algoritmih. Problem odločanja, če je dano vpeto drevo grafa tudi ... iskalno drevo določenega iskanja na tem grafu, je uvedel Hagerup leta 1985, kjer je avtor pokazal, da je ta problem učinkovito rešljiv za drevesa pri iskanju v globino (DFS) in širino (BFS). Če takšno iskalno drevo definiramo na enak način kot za BFS, to je tako, da povežemo vsako točko s svojim prvim sosedom, potem temu rečemo ▫${\cal F}$▫-drevo. Če ga po drugi strani povežemo z njegovim nazadnje obiskanim sosedom (kot v DFS), temu rečemo ▫${\cal L}$▫-drevo. V tem prispevku obravnavamo povezane paradigme iskanja. Dokazujemo, da je problem drevesa iskanja mogoče rešiti v polinomskem času za ▫$\cal L$▫-drevesa leksikografskega iskanja v globino, medtem ko je problem prepoznavanja ▫$\cal F$▫-dreves NP-poln za leksikografsko iskanje v širino, leksikografsko iskanje v globino, iskanje po največji kardinalnosti in iskanje po največji soseščini. Poleg tega predstavljamo polinomske rezultate za obe vrsti dreves na tetivnih grafih.
    Source: SIAM journal on discrete mathematics. - ISSN 0895-4801 (Vol. 35, no. 2, 2021, str. 1418-1446)
    Type of material - article, component part
    Publish date - 2021
    Language - english
    COBISS.SI-ID - 80433667

    Link(s):

    https://epubs.siam.org/doi/10.1137/20M1313301
    Repository of University of Primorska - RUP
    DOI

Shelf entry