Jesse Beisegel (Avtor), Carolin Denkert (Avtor), Ekkehard Köhler (Avtor), Matjaž Krnc (Avtor), Nevena Mitrović (Avtor), Robert Scheffler (Avtor), Martin Strehler (Avtor)

Povzetek

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.

Ključne besede

prepoznavanje iskalnih dreves;LBFS;LDFS;MNS;MCS;tetivni grafi;search tree recognition;chordal graphs;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UP - Univerza na Primorskem
UDK: 519.17
COBISS: 80433667 Povezava se bo odprla v novem oknu
ISSN: 0895-4801
Št. ogledov: 852
Št. prenosov: 23
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Problem prepoznavanja iskalnih dreves
Sekundarni povzetek: Graph searches and the corresponding search trees can exhibit important structural properties and are used in various graph algorithms. The problem of deciding whether a given spanning tree of a graph is a search tree of a particular search on this graph was introduced by Hagerup in 1985, where the author showed that this problem is efficiently solvable for depth first search (DFS) trees and breadth first search (BFS) trees. If one defines such a search tree in the same way as done for BFS, i.e., by connecting every vertex to its first neighbor, then we call this an ▫${\cal F}$▫-tree. If, on the other hand, we connect it with its most recently visited neighbor (as in DFS) we call this an ▫${\cal L}$▫-tree. In this paper, we consider related search paradigms. We prove that the search tree problem can be solved in polynomial time for ▫${\cal L}$▫-trees of lexicographic depth first search, whereas the ▫${\cal F}$▫-tree recognition problem is ▫$\mathcal{NP}$▫-complete for lexicographic breadth first search, lexicographic depth first search, maximum cardinality search, and maximal neighborhood search. Furthermore, we present polynomial results for both types of trees on chordal graphs.
Sekundarne ključne besede: prepoznavanje iskalnih dreves;LBFS;LDFS;MNS;MCS;tetivni grafi;
Strani: str. 1418-1446
Letnik: ǂVol. ǂ35
Zvezek: ǂno. ǂ2
Čas izdaje: 2021
DOI: 10.1137/20M1313301
ID: 13539670