Clean Water Pipeline Network Optimization using Minimum Spanning Tree Algorithms in Argopuro Housing, Jember

Agustina Pradjaningsih, Audy Putri Lestari, Firda Fadri, Apriani Soepardi

Abstract


Infrastructure development requires cost-efficient planning to ensure sustainable urban services. This study optimized the clean water pipeline network in Argopuro Housing, Jember, using Minimum Spanning Tree algorithms. The system was modeled as a weighted undirected graph representing junctions and pipe segments. Four algorithms Prim’s, Kruskal’s, Sollin’s, and Borůvka’s were applied to determine the optimal configuration and evaluate computational performance. All algorithms produced the same optimal pipeline length of approximately 31.00 km, representing a 40.24% reduction from the initial network. Execution time differed, with Prim’s algorithm being the fastest (0.0008 s), followed by Kruskal’s (0.0012 s), Borůvka’s (0.0067 s), and Sollin’s (0.2476 s). These results demonstrate that MST-based optimization effectively improves network efficiency. However, the study was limited to a single dataset and pipeline length as the main criterion. Future research should incorporate additional constraints and larger network scenarios for broader applicability.

Keywords


Boruvka Algorithm; Kruskal Algorithm; Minimum Spanning Tree (MST); Prim Algorithm; Solin Algorithm.

Full Text:

PDF

References


A. Łukaszewski and Ł. Nogal, “The Application of the Modified Prim ’ s Algorithm to Restore the Power System Using Renewable Energy Sources,” Symmetry (Basel)., vol. 14, no. 5, 2022, doi: 10.3390/sym14051012.

K. Kusnadi, W. Gata, and F. N. Arviantino, “Application of Kruskal and Sollin Algorithms on the National Transmission Network of South Sulawesi Province,” METIK J. (Media Teknol. Inf. dan Komputer)., vol. 6, no. 1, 2022, doi: 10.47002/metik.v6i1.260.

N. W. Wisesa and R. fitri Mawardiningrum, “Analysis of the Use of the Boruvka Algorithm Method in Electricity,” Int. J. Sci. Math. Educ., vol. 1, no. 1, pp. 29–35, 2024, doi: 10.62951/ijsme.v1i1.14.

N. J. Triami, Y. Yundari, and F. Fran, “MINIMUM SPANNING TREE PADA JARINGAN FIBER OPTIC DI UNIVERSITAS TANJUNGPURA,” Bimaster Bul. Ilm. Mat. Stat. dan Ter., vol. 09, no. 1, pp. 223–230, 2020, doi: 10.26418/bbimst.v9i1.38909.

R. Efendi, B. Susilo, and Y. A. Prasetyo, “Perbandingan Algoritma Boruvka dan Algoritma Sollin pada Optimasi Kebutuhan Kabel Fiber Optik Universitas Bengkulu,” J. Sci. Appl. Informatics, vol. 4, no. 2, pp. 175–181, 2021, doi: 10.36085/jsai.v4i2.1623.

S. Syahdan and A. Efendy, “Penerapan Algoritma Sollin Pada Jaringan Kabel Telkom Tanjung Selor Berbantu Maple,” JSB J. Sains Benuanta, vol. 2, no. 1, pp. 1–8, 2023, doi: 10.61323/jsb.v2i1.

H. M. Saad et al., “Enhancing energy balance in wireless sensor networks through optimized minimum spanning tree,” PeerJ Comput. Sci., vol. 10, pp. 1–26, 2024, doi: 10.7717/peerj-cs.2269.

D. A. Samalna, V. R. Nwokam, J. M. Ngossaha, I. Tchappi, A. A. A. Ari, and K. Kolyang, “Optimization of cyber-physical urban mobility systems in developing countries: A dependency structure matrix approach with advanced artificial intelligence techniques,” J. Infrastruct. Policy Dev., vol. 8, no. 14, p. 8126, Nov. 2024, doi: 10.24294/jipd8126.

A. Tamber, F. Ikpotokin, and O. Linus, “The Minimum Spanning Tree of the Nigeria Roads Network through Multiple-Roads Network System,” Niger. Ann. PURE Appl. Sci., vol. 3, no. 2, pp. 151–157, Jul. 2020, doi: 10.46912/napas.170.

N. Made, A. Ulandari, and S. Subarinah, “Implementasi Algoritma Kruskal dalam Menentukan Rute Terdekat pada Tempat Pariwisata di Daerah Lombok Tengah,” Griya J. Math. Appl., vol. 1, pp. 578–589, 2021, doi: 10.29303/griya.v1i4.117.

A. Ahsanti, A. Insyafilla, N. N. Fatimah, W. C. D. Wahyuni, and D. Rahmadi, “Optimalisasi Jaringan Jalan Antar Kecamatan dengan Minimum Spanning Tree dan Algoritma Prim di Kabupaten Ngawi,” Basis J. Ilm. Mat., vol. 4, no. 1, pp. 1–11, Mar. 2025, doi: 10.30872/basis.v4i1.1451.

T. Moyo, A. Y. Kibangou, and W. Musakwa, “Societal context-dependent multi-modal transportation network augmentation in Johannesburg, South Africa,” PLoS One, vol. 16, no. 4, p. e0249014, Apr. 2021, doi: 10.1371/journal.pone.0249014.

H. Wen, Y. Ye, and L. Zhang, “Optimizing road networks in underdeveloped regions for improving comprehensive efficiency integrated by accessibility, vulnerability and socioeconomic interaction,” Reliab. Eng. Syst. Saf., vol. 243, p. 109848, Mar. 2024, doi: 10.1016/j.ress.2023.109848.

I. S. Sinaga, N. Rarasati, W. Syafmen, and G. Kholijah, “MST dalam Perencanaan Jaringan Pipa Air Minum dengan Perbandingan Matriks Ketetanggaan Berbobot dan Algoritma Sollin,” FIBONACCI J. Pendidik. Mat. dan Mat., vol. 9, no. 2, pp. 179–196, 2023, doi: 10.24853/fbc.9.2.179-196.

W. I. Ilahy, M. Ahmad, and B. P. Hartono, “Optimasi Jaringan Distribusi Air di Desa Gombolharjo Menggunakan Algoritma Prim,” JaMES J. Math. Educ. Sci., vol. 6, no. 2, pp. 177–183, 2023, doi: 10.32665/james.v6i2.1896.

R. L. Graham and P. Hell, “On the History of the Minimum Spanning Tree Problem,” Ann. Hist. Comput., vol. 7, no. 1, pp. 43–57, 1985, doi: 10.1109/MAHC.1985.10011.

A. K. Nemani and R. K. Ahuja, “Minimum Spanning Trees,” Wiley Encycl. Oper. Res. Manag. Sci., 2011, doi: 10.1002/9780470400531.eorms0816.

S. Pettie, “Minimum Spanning Trees,” Encycl. Algorithms, pp. 1322–1325, 2016, doi: 10.1007/978-1-4939-2864-4_239.

H. A. Taha, Operations Research An Introduction. 2017. [Online]. Available: https://elibrary.pearson.de/book/99.150005/9781292165561

J. Joseph B. Kruskal, 17 : On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. 1956. doi: 10.7551/mitpress/12274.001.0001.

Paryati and S. Krit, “The Implementation Of Kruskal’s Algorithm For Minimum Spanning Tree In A Graph,” MATEC Web Conf. 348, vol. 01001, pp. 1–13, 2021, doi: 10.1051/matecconf/202134801001.

M. Alshammari, “Maintaining Minimum Spanning Trees in Fully Dynamic Graphs,” Int. J. Intell. Syst. Appl. Eng., vol. 12, no. 4, pp. 1562–1567, 2024, [Online]. Available: https://ijisae.org/index.php/IJISAE/article/view/6451

L. Šubelj, “Computing Well-Balanced Spanning Trees of Unweighted Networks,” Algorithms, vol. 18, no. 2, p. 760, 2025, doi: 10.3390/a18120760.

K. Tapp, “On the minimum spanning tree distribution in grids,” Eur. J. Comb., vol. 133, no. March, 2026, doi: 10.1016/j.ejc.2025.104325.

N. R. Latha, G. Shyamala, and G. R. Prasad, “Exploring the parallel implementations of the three classical MST algorithms,” in Proceedings of the International Conference on Inventive Communication and Computational Technologies, ICICCT 2017, 2017, pp. 340–346. doi: 10.1109/ICICCT.2017.7975216.

D. Rachmawati, Herriyance, and F. Y. P. Pakpahan, “Comparative Analysis of the Kruskal and Boruvka Algorithms in Solving Minimum Spanning Tree on Complete Graph.,” in 2020 International Conference on Data Science, Artificial Intelligence, and Business Analytics, DATABIA 2020 - Proceedings (2020), 2020, pp. 55–62. doi: 10.1109/DATABIA50434.2020.9190504.

F. Marpaung and Arnita, “Comparative of prim’s and boruvka’s algorithm to solve minimum spanning tree problems,” J. Phys. Conf. Ser., vol. 1462, no. 012043, 2020, doi: 10.1088/1742-6596/1462/1/012043.

N. R. Brien, “A formal correctness proof of Boruvka’s minimum spanning tree algorithm,” 2020. doi: 10.26021/10196.

J. Chen, “The analysis and application of Prim algorithm , Kruskal algorithm , Boruvka algorithm,” Appl. Comput. Eng., vol. 19, no. 1, pp. 84–89, 2023, doi: 10.54254/2755-2721/19/20231012.

R. Zhang, “The comparison of three MST algorithms,” Appl. Comput. Eng., pp. 191–197, 2023, doi: 10.54254/2755-2721/17/20230939.

D. Kurniawan, W. Wamiliana, and C. S. N. Fauzi, “Perbandingan kompleksitas algoritma prim, algoritma kruskal, dan algoritma sollin untuk menyelesaikan masalah minimum spanning tree Title,” Komputasi, vol. 2, no. 1, pp. 60–67, 2014, doi: 10.23960/komputasi.v2i1.1005.

S. Gupta, A. Mahajan, S. Shah, and V. Negi, “Exploring the Maze: A Comparative Study of Prims and Kruskals MST Algorithms,” in 15th International Conference on Computing Communication and Networking Technologies, ICCCNT 2024 (2024), 2024, pp. 1–5. doi: 10.1109/ICCCNT61001.2024.10726020.

W. McKinney, Python for Data Analysis, 3rd ed. 2018. [Online]. Available: https://wesmckinney.com/book/




DOI: http://dx.doi.org/10.30829/zero.v10i2.28487

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

 
 
✉  Contact & Indexing
Get in touch with ZERO: Jurnal Sains, Matematika dan Terapan
Email
zero_journal@uinsu.ac.id
WhatsApp · Admin Official
085270009767