2410.20137

#1 Low-degree spanning trees of $2$-edge-connected graphs in linear time [PDF] [Copy] [Kimi] [REL]

Authors: Dariusz Dereniowski ; Janusz Dybizbański ; Przemysław Karpiński ; Michał Zakrzewski ; Paweł Żyliński

We present a simple linear-time algorithm that finds a spanning tree $T$ of a given $2$-edge-connected graph $G$ such that each vertex $v$ of $T$ has degree at most $\lceil \frac{\deg_G(v)}{2}\rceil + 1$.

Subject: Data Structures and Algorithms

Publish: 2024-10-26 10:22:53 UTC