The minimum weight directed spanning tree problem (MDTP) is a well-known combinatorial optimization problem, which is also rich in its variants. The objective of this study is to survey some extensions of the MDTP and to solve an NP-complete formulation, which incorporates three additional constraints, namely degree, hop and capacity. Two heuristic approaches are developed for generating feasible solutions. Furthermore subgradient optimization of the Lagrangean relaxation for two different formulations is employed to find lower bounds for the combined problem. In addition, linear programming is also used to find lower bounds. Finally the combined problem is solved to optimality with a branch and bound strategy based on subgradient optimization. The performances of the proposed algorithms are investigated through empirical tests and computational results are reported.

Keywords: Minimum Weight Directed Spanning Tree, Capacity Constraint, Hop Constraint, Degree Constraint, Branch and Bound.