| Naslov: | On the leaves of graph search trees |
|---|
| Avtorji: | ID Scheffler, Robert (Avtor) |
|---|
| Datoteke: |  RAZ_Scheffler_Robert_2026.pdf (515,71 KB)
MD5: 209670D7F9F983E452451BCE3618E32F
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Članek v reviji |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | ZUP - Založba Univerze na Primorskem
|
|---|
| Opis: | Graph searches and their respective search trees are widely used in algorithmic graph theory. The problem whether a given spanning tree can be a graph search tree has been considered for different searches, graph classes and search tree paradigms. Similarly, the question whether a particular vertex can be visited last by some search has been studied extensively in recent years. We combine these two problems by considering the question whether a vertex can be a leaf of a graph search tree. We show that for particular search trees, including DFS trees, this problem is easy if we allow the leaf to be the first vertex of the search ordering. We contrast this result by showing that the problem becomes hard for many searches, including DFS and BFS, if we forbid the leaf to be the first vertex. Additionally, we present several structural and algorithmic results for search tree leaves of chordal graphs. |
|---|
| Ključne besede: | graph search, graph search trees, leaves, chordal graphs |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 30.11.2025 |
|---|
| Založnik: | Založba Univerze na Primorskem |
|---|
| Leto izida: | 2026 |
|---|
| Št. strani: | 29 str. |
|---|
| Številčenje: | Vol. 26, no. 1, [article no.] P1.08 |
|---|
| PID: | 20.500.12556/RUP-22292  |
|---|
| UDK: | 51 |
|---|
| eISSN: | 1855-3974 |
|---|
| DOI: | 10.26493/1855-3974.3238.2a8 |
|---|
| Datum objave v RUP: | 21.12.2025 |
|---|
| Število ogledov: | 143 |
|---|
| Število prenosov: | 1 |
|---|
| Metapodatki: |    |
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
