approximation algorithms 1graph algorithms 1minimum degree spanning tree 1near-linear time 1spanning tree 1
From the 1 of 2 linked papers with an AI index.
2 papers
cs.DS2026
Minimum Degree Spanning Tree: -Approximation in Near-Linear Time
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak +1
The paper presents a near‑linear‑time algorithm that computes a spanning tree whose maximum degree is within a factor (1+ε) of the optimal plus one, improving previous approximatio…
cs.DS2026
Additive One Approximation for Minimum Degree Spanning Tree: Breaking the Time Barrier
Sayan Bhattacharya, Ermiya Farokhnejad, Haoze Wang
We consider the ``minimum degree spanning tree'' problem. As input, we receive an undirected, connected graph with nodes and edges, and our task is to find a spa…