The Use of Probability and Edge Analysis to Solve the Multi-Period Degree Constrained Minimum Spanning Tree Problem
Article Sidebar
Abstract
The goal of the Multiperiod Degree Constrained Minimum Spanning Tree (MPDCMST) problem is to determine the smallest weight-spanning tree that satisfies the vertex installation criterion for each period and maintains the degree requirement in each vertex. This issue emerges as a network connection problem. The degree requirement indicates the reliability of each vertex, and the vertex connection/installation requirement denotes the priority vertices that must be inserted in the network within a specific time frame. The installation is split up into multiple phases/stages. This is because of various considerations such as severe weather, budgetary limitations, etc. In this research, two algorithms for solving the MPDCMST using probability hybridized with Prim’s modification, and edge analysis are proposed. The algorithms are implemented on the undirected complete graph of orders 10 to 100. The solutions are compared with some heuristics which are already in the literature. The results show that the proposed algorithms perform better.
References
Adasme, P. and A. D. Firoozabadi (2020). Degree-Constrained-Minimum Spanning Tree Problem. Complexity, 2020(1); 1–25.
Al Etaiwi, W. M. (2014). Encryption Algorithm Using Graph Theory. Journal of Scientific Research and Reports, 3(19); 2519–2527.
Boruvka, O. (1926). O Jistém Problému Minimálním. Prace Moravske Prirodovedecke Spolecnosti, 3(3); 37–58.
Brandes, U. and Cornelsen (2009). Phylogenetic Graph Models Beyond Trees. Discrete Applied Mathematics, 157(10); 2361–2369.
Caccetta, L. and S. P. Hill (2001). A Branch and Cut Method for the Degree Constrained Minimum Spanning Tree Problem. Networks, 37; 74–83.
Caccetta, L. and Wamiliana (2001). Heuristics Algorithms for the Degree Constrained Minimum Spanning Tree Problems. In F. Ghassemi, D. Post, M. Sivapalan, and R. Vertessy, editors, Proceeding of the International Congress on Modelling and Simulation (MODSIM). Canberra, pages 2161–2166.
Deo, N. and N. Kumar (1997). Computation of Constrained Spanning Trees: A Unified Approach. In P. M. Pardalos, D. W. Hearn, and W. W. Hager, editors, Network Optimization, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, pages 194–220.
Hsu, L. H. and C. K. Lin (2009). Graph Theory and Interconnection Network. Taylor and Francis Group, LLC, New York.
Huson, D. H. and D. Bryant (2006). Application of Phylogenetic Networks in Evolutionary Studies. Molecular Biology and Evolution, 23(2); 254–267.
Junaidi, S., Wamiliana, D. Sakethi, and E. T. Baskoro (2008). Computational Aspects of Greedy Algorithm for Solving the Multi Period Degree Constrained Minimum Spanning Tree Problem. Jurnal Sains MIPA, 14(1); 1–6.
Kannimuthu, S., D. Bhanu, and K. S. Bhuvaneshwari (2020). A Novel Approach for Agricultural Decision Making Using Graph Coloring. SN Applied Sciences, 2(1); 31.
Kawakura, S. and R. Shibasaki (2018). Grouping Method Using Graph Theory for Agricultural Workers Engaging in Manual Tasks. Journal of Advanced Agricultural Technologies, 5(3); 173–181.
Kawatra, R. (2002). A Multi Period Degree Constrained Minimum Spanning Tree Problem. European Journal of Operational Research, 143(1); 53–63.
Krishnamoorthy, M., A. T. Ernst, and Y. M. Sharaila (2001). Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree. Journal of Heuristics, 7(6); 587–611.
Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceeding of the American Mathematical Society, 7(1); 48–50.
Mathur, R. and N. Adlakha (2016). A Graph Theoretic Model for Prediction of Reticulation Events and Phylogenetic Networks for DNA Sequences. Egyptian Journal of Basic and Applied Sciences, 3(3); 263–271.
Ni, B., R. Qazi, S. U. Rehman, and G. Farid (2021). Some Graph-Based Encryption Schemes. Journal of Mathematics, 2021(1); 6614172.
Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. The Bell System Technical Journal, 36(6); 1389–1401.
Priyadarsini, P. L. K. (2015). A Survey on Some Applications of Graph Theory in Cryptography. Journal of Discrete Mathematical Sciences and Cryptography, 18(3); 209–217.
Thadani, S., B. Seema, and S. Anand (2022). Applications of Graph Coloring in Various Fields. Materials Today: Proceedings, 66(Part 8); 3498–3501.
Thevenin, S., Z. Nicolas, and P. Jean-Yves (2018). Graph Multi-Coloring for a Job Scheduling Application. Discrete Applied Mathematics, 234; 218–235.
Thiessen, M., L. Quesada, and K. N. Brown (2020). Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH. In E. Hebrard and N. Musliu, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020, Lecture Notes in Computer Science, volume 12296. Springer International Publishing, Cham, pages 447–456.
Vasudev, C. (2006). Graph Theory with Applications. New Age International.
Wamiliana, Asmiati, M. Usman, A. Hijriani, and W. C. Hastono (2018). Comparative Analysis of Some Modified Prim’s Algorithms to Solve the Multiperiod Degree Constrained Minimum Spanning Tree Problem. Indian Journal of Science and Technology, 11(11); 1–6.
Wamiliana, M. Usman, F. Elfaki, and M. Azram (2015a). Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Sciences, 10(21); 10147–10152.
Wamiliana, M. Usman, D. Sakethi, and A. Cucus (2015b). The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving the Multiperiod Degree Constrained Minimum Spanning Tree Problem. In IEEE Proceeding on 4th International Conference on Interactive Digital Media (ICIDM). pages 1–4.
Wamiliana, M. Usman, W. Warsito, W. Warsono, and J. I. Daoud (2020). Using Modification of Prim’s Algorithm and GNU Octave to Solve the Multiperiods Installation Problem. IIUM Engineering Journal, 21(1); 100–112.
Zhou, G. and M. Gen (1997). A Note on Genetics Algorithms for Degree Constrained Spanning Tree Problems. Network, 30; 91–95.
Al Etaiwi, W. M. (2014). Encryption Algorithm Using Graph Theory. Journal of Scientific Research and Reports, 3(19); 2519–2527.
Boruvka, O. (1926). O Jistém Problému Minimálním. Prace Moravske Prirodovedecke Spolecnosti, 3(3); 37–58.
Brandes, U. and Cornelsen (2009). Phylogenetic Graph Models Beyond Trees. Discrete Applied Mathematics, 157(10); 2361–2369.
Caccetta, L. and S. P. Hill (2001). A Branch and Cut Method for the Degree Constrained Minimum Spanning Tree Problem. Networks, 37; 74–83.
Caccetta, L. and Wamiliana (2001). Heuristics Algorithms for the Degree Constrained Minimum Spanning Tree Problems. In F. Ghassemi, D. Post, M. Sivapalan, and R. Vertessy, editors, Proceeding of the International Congress on Modelling and Simulation (MODSIM). Canberra, pages 2161–2166.
Deo, N. and N. Kumar (1997). Computation of Constrained Spanning Trees: A Unified Approach. In P. M. Pardalos, D. W. Hearn, and W. W. Hager, editors, Network Optimization, Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, pages 194–220.
Hsu, L. H. and C. K. Lin (2009). Graph Theory and Interconnection Network. Taylor and Francis Group, LLC, New York.
Huson, D. H. and D. Bryant (2006). Application of Phylogenetic Networks in Evolutionary Studies. Molecular Biology and Evolution, 23(2); 254–267.
Junaidi, S., Wamiliana, D. Sakethi, and E. T. Baskoro (2008). Computational Aspects of Greedy Algorithm for Solving the Multi Period Degree Constrained Minimum Spanning Tree Problem. Jurnal Sains MIPA, 14(1); 1–6.
Kannimuthu, S., D. Bhanu, and K. S. Bhuvaneshwari (2020). A Novel Approach for Agricultural Decision Making Using Graph Coloring. SN Applied Sciences, 2(1); 31.
Kawakura, S. and R. Shibasaki (2018). Grouping Method Using Graph Theory for Agricultural Workers Engaging in Manual Tasks. Journal of Advanced Agricultural Technologies, 5(3); 173–181.
Kawatra, R. (2002). A Multi Period Degree Constrained Minimum Spanning Tree Problem. European Journal of Operational Research, 143(1); 53–63.
Krishnamoorthy, M., A. T. Ernst, and Y. M. Sharaila (2001). Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree. Journal of Heuristics, 7(6); 587–611.
Kruskal, J. B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceeding of the American Mathematical Society, 7(1); 48–50.
Mathur, R. and N. Adlakha (2016). A Graph Theoretic Model for Prediction of Reticulation Events and Phylogenetic Networks for DNA Sequences. Egyptian Journal of Basic and Applied Sciences, 3(3); 263–271.
Ni, B., R. Qazi, S. U. Rehman, and G. Farid (2021). Some Graph-Based Encryption Schemes. Journal of Mathematics, 2021(1); 6614172.
Prim, R. C. (1957). Shortest Connection Networks and Some Generalizations. The Bell System Technical Journal, 36(6); 1389–1401.
Priyadarsini, P. L. K. (2015). A Survey on Some Applications of Graph Theory in Cryptography. Journal of Discrete Mathematical Sciences and Cryptography, 18(3); 209–217.
Thadani, S., B. Seema, and S. Anand (2022). Applications of Graph Coloring in Various Fields. Materials Today: Proceedings, 66(Part 8); 3498–3501.
Thevenin, S., Z. Nicolas, and P. Jean-Yves (2018). Graph Multi-Coloring for a Job Scheduling Application. Discrete Applied Mathematics, 234; 218–235.
Thiessen, M., L. Quesada, and K. N. Brown (2020). Improving a Branch-and-Bound Approach for the Degree-Constrained Minimum Spanning Tree Problem with LKH. In E. Hebrard and N. Musliu, editors, Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2020, Lecture Notes in Computer Science, volume 12296. Springer International Publishing, Cham, pages 447–456.
Vasudev, C. (2006). Graph Theory with Applications. New Age International.
Wamiliana, Asmiati, M. Usman, A. Hijriani, and W. C. Hastono (2018). Comparative Analysis of Some Modified Prim’s Algorithms to Solve the Multiperiod Degree Constrained Minimum Spanning Tree Problem. Indian Journal of Science and Technology, 11(11); 1–6.
Wamiliana, M. Usman, F. Elfaki, and M. Azram (2015a). Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Sciences, 10(21); 10147–10152.
Wamiliana, M. Usman, D. Sakethi, and A. Cucus (2015b). The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving the Multiperiod Degree Constrained Minimum Spanning Tree Problem. In IEEE Proceeding on 4th International Conference on Interactive Digital Media (ICIDM). pages 1–4.
Wamiliana, M. Usman, W. Warsito, W. Warsono, and J. I. Daoud (2020). Using Modification of Prim’s Algorithm and GNU Octave to Solve the Multiperiods Installation Problem. IIUM Engineering Journal, 21(1); 100–112.
Zhou, G. and M. Gen (1997). A Note on Genetics Algorithms for Degree Constrained Spanning Tree Problems. Network, 30; 91–95.
Authors
Wamiliana, Junaidi, A., Gamal, M. D. H., & Thamrin, T. (2024). The Use of Probability and Edge Analysis to Solve the Multi-Period Degree Constrained Minimum Spanning Tree Problem. Science and Technology Indonesia, 9(4), 999–1008. https://doi.org/10.26554/sti.2024.9.4.999-1008
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.