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

Autor:	Dereniowski, Dariusz, Dybizbański, Janusz, Karpiński, Przemysław, Zakrzewski, Michał, Żyliński, Paweł
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms G.2.2 F.2.2
Druh dokumentu:	Working Paper
Popis:	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$.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.20137 Zobrazit plný text záznamu View this record from Arxiv