12 papers:
ICALP-v1-2012-MegowSVW #online #power of- The Power of Recourse for Online MST and TSP (NM, MS, JV, AW), pp. 689–700.
- ICALP-2007-CaragiannisFM #ad hoc #energy #exponential #heuristic #network
- An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks (IC, MF, LM), pp. 447–458.
- ICALP-v1-2006-Fujito #algorithm #approximate #how
- How to Trim an MST: A 2-Approximation Algorithm for Minimum Cost Tree Cover (TF), pp. 431–442.
STOC-2005-Garg #approximate #graph #problem- Saving an epsilon: a 2-approximation for the k-MST problem in graphs (NG), pp. 396–402.
- ICALP-2005-Ambuhl #algorithm #bound #energy #network #performance
- An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks (CA), pp. 1139–1150.
- STOC-2003-KonemannR #approximate #bound
- Primal-dual meets local search: approximating MST’s with nonuniform degree bounds (JK, RR), pp. 389–395.
- ICALP-2003-AroraC #approximate #problem #strict
- Approximation Schemes for Degree-Restricted MST and Red-Blue Separation Problem (SA, KLC), pp. 176–188.
LCTES-SCOPES-2002-ChoPW #algorithm #architecture #graph #memory management #performance- Efficient register and memory assignment for non-orthogonal architectures via graph coloring and MST algorithms (JC, YP, DBW), pp. 130–138.
- STOC-1998-BuchsbaumKRW #algorithm #linear #verification
- Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators (ALB, HK, AR, JW), pp. 279–288.
- STOC-1997-Trevisan #geometry
- When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract) (LT), pp. 21–29.
- STOC-1996-BlumRV #algorithm #approximate #problem
- A Constant-factor Approximation Algorithm for the k MST Problem (Extended Abstract) (AB, RR, SV), pp. 442–448.
- STOC-1995-BlumCV #approximate #problem
- A constant-factor approximation for the k-MST problem in the plane (AB, PC, SV), pp. 294–302.
