Back to Search Start Over

Low-degree spanning trees of $2$-edge-connected graphs in linear time

Authors :
Dereniowski, Dariusz
Dybizbański, Janusz
Karpiński, Przemysław
Zakrzewski, Michał
Żyliński, Paweł
Publication Year :
2024

Abstract

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$.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2410.20137
Document Type :
Working Paper