PENGGUNAAN METODE CUTTING PLANE UNTUK MENYELESAIKAN MINIMUM SPANNING TREE DENGAN KENDALA BOBOT PADA GRAF K_n

Dewi Suhika, Wamiliana Wamiliana

Abstract


This study aims to determine the minimum spanning tree of a complete graph K_n with weight constraints and completion using the cutting plane method. The cutting plane method is one of the algorithms included in the exact method. This algorithm works by reducing the solution area so that it becomes narrower. As a result, the feasible solutions that will be investigated become less and less. This is because the cutting plane method works based on the optimal linear programming solution of relaxation solved by the simplex method. In this paper we give illustration of the algorithm applied for two cases, one for K_4 and one for K_5.

Keywords


complete graph; tree; minimum spanning tree; cutting plane method



DOI: http://dx.doi.org/10.24127/ajpm.v7i1.1353

Refbacks

  • There are currently no refbacks.


Indexing by: