SOLUTION OF KNAPSACK CONSTRAINED MAXIMUM SPANNING TREEE PROBLEM USING KRUSKAL ALGORITHM

Puspita, Ika and Sigit, Nugroho and Yulian, Fauzi (2009) SOLUTION OF KNAPSACK CONSTRAINED MAXIMUM SPANNING TREEE PROBLEM USING KRUSKAL ALGORITHM. Undergraduated thesis, Fakultas Matematika Dan Ilmu Pengetahuan Alam UNIB.

Text SKRIPSI IKA PUSPITA_F1A005028.pdf - Bibliography Restricted to Registered users only Available under License Creative Commons GNU GPL (Software). Download (3MB)

Abstract

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.

Actions (login required)

View Item