Low-degree spanning trees of 2-edge-connected graphs in linear time
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$$ .
Authors
- Paweł Żyliński (ORCID: https://orcid.org/0000-0001-6378-7742)
- Dariusz Dereniowski (ORCID: https://orcid.org/0000-0003-4000-4818)
- Janusz Dybizbański (ORCID: https://orcid.org/0000-0002-2575-4373)
- Przemysław Karpiński
- Michał Zakrzewski (ORCID: https://orcid.org/0000-0003-4845-7707)
Institutions
- Gdańsk University of Technology (PL)
- University of Gdańsk (PL)
- Intel (Poland) (PL)
Publication Details
- Journal
- Journal of Combinatorial Optimization
- Published
- 2025-10-25
- DOI
- https://doi.org/10.1007/s10878-025-01368-2
- Primary Topic
- Interconnection Networks and Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Intel Corporation