Before revision: We develop fast near-linear time approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem  and its generalization the Crossing Spanning Tree problem  .
After revision: We develop fast near-linear time approximation algorithms for the minimum-cost version of the Bounded-Degree MST problem and its generalization the Crossing Spanning Tree problem (Crossing-ST) .