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

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:
Typology: 1.01 - Original Scientific Article
Organization: UP - University of Primorska
UDC: 519.17
COBISS: 80433667 Link will open in a new window
ISSN: 0895-4801
Views: 852
Downloads: 23
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

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