On Kernels and Leaves: Searching for Bare and Lush Trees

Jesse Beisegel, Ekkehard Köhler, Robert Scheffler +1

We study a variation of the classical Maximum (Minimum) Leaf Spanning Tree problem. In many applications, Depth-First Search (DFS) is used to compute a spanning tree of a graph. Su…