{"?xml":{"@version":"1.0"},"edm:RDF":{"@xmlns:dc":"http://purl.org/dc/elements/1.1/","@xmlns:edm":"http://www.europeana.eu/schemas/edm/","@xmlns:wgs84_pos":"http://www.w3.org/2003/01/geo/wgs84_pos","@xmlns:foaf":"http://xmlns.com/foaf/0.1/","@xmlns:rdaGr2":"http://rdvocab.info/ElementsGr2","@xmlns:oai":"http://www.openarchives.org/OAI/2.0/","@xmlns:owl":"http://www.w3.org/2002/07/owl#","@xmlns:rdf":"http://www.w3.org/1999/02/22-rdf-syntax-ns#","@xmlns:ore":"http://www.openarchives.org/ore/terms/","@xmlns:skos":"http://www.w3.org/2004/02/skos/core#","@xmlns:dcterms":"http://purl.org/dc/terms/","edm:WebResource":[{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-J2K09WER/3761e853-8e12-438a-bb74-e54fb2951966/PDF","dcterms:extent":"515 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-J2K09WER/0d5df1b1-beea-4078-8239-7abeff2f3f57/TEXT","dcterms:extent":"89 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-J2K09WER/30d808c9-a6e9-4a62-aa5f-cc3d20e9da12/PDF","dcterms:extent":"93 KB"},{"@rdf:about":"http://www.dlib.si/stream/URN:NBN:SI:doc-J2K09WER/032de59b-6cad-4a6c-8cc3-5f0acafe487c/TEXT","dcterms:extent":"3 KB"}],"edm:ProvidedCHO":{"@rdf:about":"URN:NBN:SI:doc-J2K09WER","dcterms:issued":"2026","dc:creator":"Scheffler, Robert","dc:format":[{"@xml:lang":"sl","#text":"številka:1, article  p1.08"},{"@xml:lang":"sl","#text":"letnik:26"},{"@xml:lang":"sl","#text":"str. 1-29"}],"dc:identifier":["DOI:10.26493/1855-3974.3238.2a8","ISSN:1855-3974","COBISSID_HOST:288373763","URN:URN:NBN:SI:doc-J2K09WER"],"dc:language":"en","dc:publisher":{"@xml:lang":"sl","#text":"Univerza na Primorskem"},"dc:source":{"@xml:lang":"sl","#text":"Ars mathematica contemporanea"},"dc:subject":[{"@xml:lang":"sl","#text":"akordni grafi"},{"@xml:lang":"en","#text":"chordal graphs"},{"@xml:lang":"en","#text":"graph search"},{"@xml:lang":"en","#text":"graph search trees"},{"@xml:lang":"sl","#text":"iskalna drevesa grafov"},{"@xml:lang":"sl","#text":"iskanje v grafu"},{"@xml:lang":"en","#text":"leaves"},{"@xml:lang":"sl","#text":"listi"}],"dc:title":{"@xml:lang":"sl","#text":"On the leaves of graph search trees|"},"dc:description":[{"@xml:lang":"sl","#text":"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"},{"@xml:lang":"sl","#text":"Iskanja v grafih in njihova ustrezna iskalna drevesa so široko uporabljena v algoritmični teoriji grafov. Problem, ali je dano vpeto drevo lahko iskalno drevo grafa, je bil obravnavan za različna iskanja, razrede grafov in paradigme iskalnih dreves. Podobno je bilo vprašanje, ali je lahko določeno vozlišče obiskano zadnje pri nekem iskanju, v zadnjih letih obsežno raziskano. Združujemo ti dve vprašanji z obravnavo vprašanja, ali je lahko vozlišče list iskalnega drevesa grafa. Pokažemo, da je za določena iskalna drevesa, vključno z DFS drevesi, ta problem enostaven, če dovolimo, da je list prvo vozlišče v iskalnem urejanju. Ta rezultat postavimo v kontrast s tem, da pokažemo, kako problem postane težaven za mnoga iskanja, vključno z DFS in BFS, če prepovemo, da je list prvo vozlišče. Poleg tega predstavimo več strukturnih in algoritmičnih rezultatov za liste iskalnih dreves akordnih grafov"}],"edm:type":"TEXT","dc:type":[{"@xml:lang":"sl","#text":"znanstveno časopisje"},{"@xml:lang":"en","#text":"journals"},{"@rdf:resource":"http://www.wikidata.org/entity/Q361785"}]},"ore:Aggregation":{"@rdf:about":"http://www.dlib.si/?URN=URN:NBN:SI:doc-J2K09WER","edm:aggregatedCHO":{"@rdf:resource":"URN:NBN:SI:doc-J2K09WER"},"edm:isShownBy":{"@rdf:resource":"http://www.dlib.si/stream/URN:NBN:SI:doc-J2K09WER/3761e853-8e12-438a-bb74-e54fb2951966/PDF"},"edm:rights":{"@rdf:resource":"http://creativecommons.org/licenses/by/4.0/"},"edm:provider":"Slovenian National E-content Aggregator","edm:intermediateProvider":{"@xml:lang":"en","#text":"National and University Library of Slovenia"},"edm:dataProvider":{"@xml:lang":"sl","#text":"Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije"},"edm:object":{"@rdf:resource":"http://www.dlib.si/streamdb/URN:NBN:SI:doc-J2K09WER/maxi/edm"},"edm:isShownAt":{"@rdf:resource":"http://www.dlib.si/details/URN:NBN:SI:doc-J2K09WER"}}}}