1. On the leaves of graph search treesRobert Scheffler, 2026, izvirni znanstveni članek 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
Objavljeno v RUP: 21.12.2025; Ogledov: 226; Prenosov: 2
 Celotno besedilo (515,71 KB) |
2. The recognition problem of graph search trees read moreJesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2021, izvirni znanstveni članek Ključne besede: search tree recognition, LBFS, LDFS, MNS, MCS, chordal graphs
Objavljeno v RUP: 18.10.2021; Ogledov: 3722; Prenosov: 31
 Povezava na celotno besedilo |
3. Edge elimination and weighted graph classesJesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Martin Milanič, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, objavljeni znanstveni prispevek na konferenci Ključne besede: edge elimination, weighted graph, split graph, threshold graph, chain graph, linear-time recognition algorithm
Objavljeno v RUP: 10.11.2020; Ogledov: 3092; Prenosov: 38
Povezava na celotno besedilo |
4. Edge elimination schemes of weighted graph classes, Workshop on Graph Modification algorithms, experiments and new problems, 23rd - 24th January 2020, Bergen, NorwayMartin Milanič, Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2020, vabljeno predavanje na konferenci brez natisa Ključne besede: graph class, edge elimination scheme, sandwich monotonicity
Objavljeno v RUP: 28.05.2020; Ogledov: 3115; Prenosov: 0 |
5. On the end-vertex problemJesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2018, objavljeni povzetek znanstvenega prispevka na konferenci Ključne besede: graph search, maximum cardinality search, maximal neighborhood search, graph classes
Objavljeno v RUP: 28.05.2020; Ogledov: 2964; Prenosov: 102
Celotno besedilo (1,85 MB)
Gradivo ima več datotek! Več... |
6. Recognizing graph search treesJesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2019, izvirni znanstveni članek Ključne besede: search tree recognition, LBFS, LDFS, MNS, MCS
Objavljeno v RUP: 16.10.2019; Ogledov: 3671; Prenosov: 76
Povezava na celotno besedilo |
7. On the end-vertex problem of graph searchesJesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, Martin Strehler, 2019, izvirni znanstveni članek Ključne besede: end-vertex, graph search, maximum cardinality search, maximal neighborhood search, graph classes
Objavljeno v RUP: 22.08.2019; Ogledov: 3052; Prenosov: 52
Povezava na celotno besedilo |
