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

Authors

  • Dewi Suhika Institut Teknologi Sumatera
  • Wamiliana Wamiliana Universitas Lampung

DOI:

https://doi.org/10.24127/ajpm.v7i1.1353

Keywords:

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

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.

Author Biographies

Dewi Suhika, Institut Teknologi Sumatera

Matematics Department

Wamiliana Wamiliana, Universitas Lampung

Mathematics Department

References

Bronson, R. 1996. Teori dan Soal-Soal Operation Research. Jakarta: Erlangga.

Deo, N. 1989. Graph Theory with Aplications to Engineering and Computer Science. Prentice Hall, Inc. Englewood Cliffs, New Jersey. Hal. 461.

Henn, T. S. 2007. Weight-Constrained Minimum Spanning Tree Problem. Diploma Thesis: University of Kaiserslautern Departement of Mathematics. Hal 7-25.

Munir, R. 2012. Matematika Diskrit. Bandung: Informatika.

Nurbaiti, Wahyuni. 2015. Aplikasi Minimum Spanning Tree Pada Jaringan Listrik Di Perumahan Mutiara Indah Village. Jurnal MSA. Vol. 3 No. 1, Hal 47-56.

Siang, J.J. 2009. Matematika Diskrit dan Aplikasinya pada Ilmu Komputer. Yogyakarta: ANDI

Subagyo, P., Asri, M., Handoko, T.H. 2009. Dasar-Dasar Operations Research. Yogyakarta: BPEE.

Wamiliana. 2015. Program Linear Teori dan Terapannya. CV Anugrah Utama Raharja (AURA), Bandar Lampung.

Downloads

Published

11-06-2018

Issue

Vol. 7 No. 1 (2018)

Section

Articles

License

Authors who publish with AKSIOMA: Jurnal Program Studi Pendidikan Matematika agree to the following terms:

Creative Commons License
Creative Commons License
AKSIOMA: Jurnal Program Studi Pendidikan Matematika is licensed under a Creative Commons Attribution 4.0 International License.

This journal provides immediate open access to its content on the principle that making research freely available to the public supports a greater global exchange of knowledge. AKSIOMA offers all authors of journal articles allows their research openly available, free access and time restrictions.

All articles published Open Access will be immediately and permanently free for everyone to read and download. Under the CC-BY license, authors retain ownership of the copyright for their article, but authors grant others permission to use the content of publications in AKSIOMA in whole or in part provided that the original work is properly cited. Users (redistributors) of AKSIOMA are required to cite the original source, including the author's names, AKSIOMA as the initial source of publication, year of publication, volume number and DOI (if available).