6 papers
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 the 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…
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…