Abstract
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.
Keywords
prepoznavanje iskalnih dreves;LBFS;LDFS;MNS;MCS;tetivni grafi;search tree recognition;chordal graphs;
Data
Language: |
English |
Year of publishing: |
2021 |
Typology: |
1.01 - Original Scientific Article |
Organization: |
UP - University of Primorska |
UDC: |
519.17 |
COBISS: |
80433667
|
ISSN: |
0895-4801 |
Views: |
852 |
Downloads: |
23 |
Average score: |
0 (0 votes) |
Metadata: |
|
Other data
Secondary language: |
English |
Secondary title: |
Problem prepoznavanja iskalnih dreves |
Secondary abstract: |
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. |
Secondary keywords: |
prepoznavanje iskalnih dreves;LBFS;LDFS;MNS;MCS;tetivni grafi; |
Pages: |
str. 1418-1446 |
Volume: |
ǂVol. ǂ35 |
Issue: |
ǂno. ǂ2 |
Chronology: |
2021 |
DOI: |
10.1137/20M1313301 |
ID: |
13539670 |