SOLUTION OF KNAPSACK CONSTRAINED MAXIMUM SPANNING TREEE PROBLEM USING KRUSKAL ALGORITHM
| Main Authors: | Puspita, Ika, Sigit, Nugroho, Yulian, Fauzi |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | eng |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://repository.unib.ac.id/3331/1/SKRIPSI%20IKA%20PUSPITA_F1A005028.pdf http://repository.unib.ac.id/3331/ |
Daftar Isi:
- 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.