4 papers
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…
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…
Lower bounds on collective additive spanners
Derek G. Corneil, Feodor F. Dragan, Ekkehard Köhler +1
In this paper we present various lower bound results on collective tree spanners and on spanners of bounded treewidth. A graph is said to admit a system of collective addi…
Graph parameters that are coarsely equivalent to path-length
Feodor F. Dragan, Ekkehard Köhler
Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph . Recently, several graph parameters were shown to be…