SOLUTION OF KNAPSACK CONSTRAINED MAXIMUM SPANNING TREEE PROBLEM USING KRUSKAL ALGORITHM

Knapsack Constrained Maximum Spanning Tree (KCMST) problem is
optimization problem combining problem of Knapsack and maximum spanning
tree. This problem of KCMST is used for maximizing profit with respect to
limited price (cost). This research objective is to model a graph problem into
KCMST using Lagrange Multiplier approach and finding its optimal solution
using Bisection method and Kruskal algorithm. The graph case in which KCMST
is modelled and solved is a graph with 10 vertices and 17 edges and Kanpsack
capacity 400. So far this study has resulted in maximum profit of 518 and
minimum cost of 381. The solution has been obtained through 12 iteration with
error of 0.005. The other case using 20 vertices and 46 edges with capacity of
Knapsack 600 has given a maximum profit of 1221 with price of 540 through 12
iteration with error 0.005.