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

2024/10/26 by Dereniowski, Dariusz, Dybizbański, Janusz, Karpiński, Przemysław +2
#Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #G.2.2

paper · doi:10.48550/arxiv.2410.20137

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 (°_G(v))/(2)\rceil + 1.

Related

• Near-linear Time Algorithm for Approximate Minimum Degree Spanning Trees
• Edge Disjoint Spanning Trees in an Undirected Graph with E=2(V-1)
• Spanning trees without adjacent vertices of degree 2
• Spanning trees with few branch vertices
• Binary weights spanning trees and the k-red spanning tree problem in linear time