8 citations · 17 across the 9 of their papers we have counts for
11 papers · 1 filter
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…
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…
Characterising AT-free Graphs with BFS
Jesse Beisegel
An asteroidal triple free graph is a graph such that for every independent triple of vertices no path between any two avoids the third. In a recent result from Corneil and Stacho,…