3 papers
cs.DS2026
Breadth-First Search Trees with Many or Few Leaves
Jesse Beisegel, Ekkehard Köhler, Robert Scheffler +1
The Maximum (Minimum) Leaf Spanning Tree problem asks for a spanning tree with the largest (smallest) number of leaves. As spanning trees are often computed using graph search algo…
cs.DM2025
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…
cs.GT2025
On the Price of Anarchy in Packet Routing Games with FIFO
Daniel Schmand, Torben Schürenberg, Martin Strehler
We investigate packet routing games in which network users selfishly route themselves through a network over discrete time, aiming to reach the destination as quickly as possible.…