Showing cs.DMShow all
3 papers · 1 filter
cs.DM2025
Sandwich Monotonicity and Recognition of Weighted Graph Classes
Jesse Beisegel, Nina Chiarelli, Ekkehard Köhler +9
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…
cs.DM2024
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…
cs.DM2024
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…