Minimal spanning tree subject to a side constraint

This paper addresses the problem of finding a minimal spanning tree in a network subject to a knapsack-type constraint. The problem is shown to belong to the class of NP -complete problems. Certain properties of an optimal solution to this problem are established considering a bicriteria spanning tree problem. Based on these, an algorithm is proposed which is mainly a branch and bound scheme branching from the test upper bound and generating efficient frontiers successively. It also uses certain effective heuristics and bounds that are obtained in polynomially bounded operations. The algorithm is validated and a numerical example is included.