Back to Search
Start Over
Low-degree spanning trees of $2$-edge-connected graphs in linear time
- 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$.
- Subjects :
- Computer Science - Data Structures and Algorithms
G.2.2, F.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2410.20137
- Document Type :
- Working Paper