8 citations · 19 across the 10 of their papers we have counts for
16 papers
On Kernels and Leaves: Searching for Bare and Lush Trees
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler +1
We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Su…
Generalized Graph Search Trees
Florian Krowiorz, Robert Scheffler
Graph search algorithms and their corresponding graph search trees are commonly used in algorithmic graph theory. In recent years, the recognition problem of these graph search tre…
Simultaneous Graph Parameters and How to Bound Them
Robert Scheffler, Philipp Wolf Schleicher
Beisegel et al. [SWAT 2024] introduced the concept of simultaneous -numbers which associate a graph class with a graph parameter. Given a graph , the…
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles II: Vertex and Edge Deletion Numbers
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path or cycle with precedence constraints in the form of a partial order on the vertex set. We study the complexity for graph width…
Sandwich Monotonicity and Recognition of Weighted Graph Classes
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +5
Edge-weighted graphs play an important role in the theory of Robinsonian matrices and similarity theory, particularly via the concept of level graphs, that is, graphs obtained from…
A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path or a Hamiltonian cycle with precedence constraints in the form of a partial order on the vertex set. We show that the path pro…
A Graph Width Perspective on Partially Ordered Hamiltonian Paths
Jesse Beisegel, Katharina Klost, Kristin Knorr +2
We consider the problem of finding a Hamiltonian path with precedence constraints in the form of a partial order on the vertex set. This problem is known as Partially Ordered Hamil…
The Simultaneous Interval Number: A New Width Parameter that Measures the Similarity to Interval Graphs
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +3
We propose a novel way of generalizing the class of interval graphs, via a graph width parameter called the simultaneous interval number. This parameter is related to the simultane…
Graph Search Trees and the Intermezzo Problem
Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak +2
The last in-tree recognition problem asks whether a given spanning tree can be derived by connecting each vertex with its rightmost left neighbor of some search ordering. In this s…
Computing Hamiltonian Paths with Partial Order Restrictions
Jesse Beisegel, Fabienne Ratajczak, Robert Scheffler
When solving the Hamiltonian path problem it seems natural to be given additional precedence constraints for the order in which the vertices are visited. For example one could deci…
Graph Search Trees and Their Leaves
Robert Scheffler
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 consider…
Linearizing Partial Search Orders
Robert Scheffler
In recent years, questions about the construction of special orderings of a given graph search were studied by several authors. On the one hand, the so called end-vertex problem in…
Linear Time LexDFS on Chordal Graphs
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler +1
Lexicographic Depth First Search (LexDFS) is a special variant of a Depth First Search (DFS), which was introduced by Corneil and Krueger in 2008. While this search has been used i…
Recognizing Graph Search Trees
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
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 span…
On the End-Vertex Problem of Graph Searches
Jesse Beisegel, Carolin Denkert, Ekkehard Köhler +4
End vertices of graph searches can exhibit strong structural properties and are crucial for many graph algorithms. The problem of deciding whether a given vertex of a graph is an e…
Nash equilibria in routing games with edge priorities
Robert Scheffler, Martin Strehler, Laura Vargas Koch
In this paper we present a new competitive packet routing model with edge priorities. We consider players that route selfishly through a network over time and try to reach their de…