Minimum Spanning Tree Approach to Path Through K Specified Links

Authors

  • Santosh Kumar Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, Australia
  • Elias Munapo School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa
  • Philimon Nyamugure Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe
  • Trust Tawanda Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

DOI:

https://doi.org/10.13052/jgeu0975-1416.1127

Keywords:

Specified links, circuits, minimum spanning tree, partially minimum spanning tree

Abstract

This paper presents a minimum spanning tree approach to find a path through ‘k’ specified links. This problem has many real-life applications and unlike the shortest route, the path through specified links may have loops. The proposed method determines the route, which may either be an optimal or a near optimal path. It may also contain loops.

Downloads

Download data is not yet available.

Author Biographies

Santosh Kumar, Department of Mathematical and Geospatial Sciences, School of Sciences, RMIT University, Melbourne, Australia

Santosh Kumar OAM received PhD degree from Delhi University in 1968. He is author and co-author of over 200 papers and 4 books in the field of Operations Research. His contributions in the field of OR have been recognised in the form of ‘Ren Pots’ award from the Australian Society for operations Research (ASOR) in 2009 and a recognition award from the South African OR Society as a non-member of the society and a non-resident of South Africa in 2011. He was the President of the Asia Pacific Operations Research societies (1995–97), where ASOR was a member along with 7 other countries in the region. He is currently an Honorary Professor at the RMIT University, Melbourne. He is a Fellow of the Institute of Mathematics and its Applications, UK. On 14th June 2021, he was awarded a medal of the Order of Australia (OAM).

Elias Munapo, School of Economics and Decision Sciences, North West University, Mafikeng Campus, Mafikeng, South Africa

Elias Munapo holds a BSc. (Hons) Applied Mathematics (1997), MSc. Operations Research (2002) and a PhD Operations Research (2010), all from the National University of science and Technology (N.U.S.T.), Zimbabwe. A certificate in outcomes-based assessment in Higher Education and Open distance learning, University of South Africa (UNISA), certificate in University Education Induction Programme, University of KwaZulu-Natal (UKZN). He is a Professional Natural Scientist certified by the South African Council for Natural Scientific Professions (SACNASP), 2012; and NRF rated in South Africa. He has published/co-published over 120 articles and two books. He has also edited/co-edited 7 books and is a guest editor of Applied Sciences, Algorithms and Next Energy journals which are under MDPI. He has supervised/co-supervised eleven doctoral students and over 30 students at Master level. He is a member of the Operations Research Society of South Africa, Executive Committee Member 2012–13, South African Council for Natural Scientific Professions (SACNASP) as a Certified Natural Scientist, European Conference on Operational Research (EURO) and the International Federation of Operations Research Societies (IFORS), and a member of the International Conference on Optimization (ICO) and is part of the team preparing to host ICO 2026 at Johannesburg.

Philimon Nyamugure, Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

Philimon Nyamugure has a BSc (Hons) 1998, MSc – 2002; Post Graduate Diploma in Higher Education, 2013, all from NUST; PhD in Statistics, University of Limpopo, 2017. He joined NUST in 2003 and was Chairperson for the Departments of Applied Mathematics (2009–2013) and Chairman, Department of Statistics and Operations Research (2013–2019). Became Executive Dean of the Faculty of Applied Science from 2020 to date. A University Senator from 2009 and Councillor from 2020 up to date. He received an award for the best PhD presenter in the School of Mathematical and Computer Sciences, University of Limpopo. Best Senior presenter, Faculty of Applied Sciences, and in 2017 Fulbright Research Award for African Scholars. Involved in several community engagement programmes including National University of Science and Technology Schools Enrichment Programme (NUSTSEP). He is currently an Executive Dean and a Professor at NUST.

Trust Tawanda, Department of Statistics and Operations Research, National University of Science and Technology, Box AC 939, Ascot, Bulawayo, Zimbabwe

Trust Tawanda received the bachelor’s degree in Operations Research and Statistics and the master’s degree in Operations Research and Statistics from the National University of Science and Technology (NUST), Zimbabwe, in 2013 and 2017 respectively, and is currently a student for the Doctor of Philosophy degree in Operations Research, NUST, Zimbabwe. He is currently working as a Lecturer at the Department of Statistics and Operations Research, Faculty of Applied Sciences, NUST. His research areas include maximum flow, shortest paths, transportation, travelling salesman and assignment problems. He has published papers and book chapters.

References

R. K. Ahuja, K. Mehlhorn, J.B. Orlin, and R.E. Tarjan, Faster algorithms for the shortest path problem, Journal of the Association of Computing Machinery, Vol. 37, pp. 213–223, 1990.

H. Arora, and S. Kumar, Path through k-specified edges in a liner graph, Opsearch, Vol. 30, No. 2, pp. 163–173, 1993.

R.E. Beckwith, Dynamic programming and network routing: An introduction to the technique of functional equations, Dynamic programming workshop, Boulder, Colorado. 1961.

R. E. Bellman, On a routing problem, Quarterly of Applied mathematics, Vol. 16, No. 1, pp. 87–90, 1958.

R. E. Bellman, Dynamic programming treatment of travelling salesman problems, J of ACM, Vol. 9, pp. 61–63, 1962.

R. E. Bellman, and R. Kalaba, On the Kth Best policies, J of Society Industrial and Applied Mathematics, Vol. 8, No. 4, pp. 582–588, 1960.

G. B. Dantzig, Discrete variable extremum problems, Opns. Res. Vol. 5, pp. 266–276, 1957.

E. J. Dijkstra, A note on two problems in connection with graphs, Numerische Mathematik. 1: 269–271, 1959, doi: 10.1007/BF01386390.S2CID123284777.

R.C. Garg, and S. Kumar, Shortest connected graph through dynamic programming, Maths Magazine, Vol. 41, No. 4, pp. 170–173, 1968.

R. Kalaba, On some communicating network problems, DOI: 10.1090/psapm/010/0122573, 1959.

J. B. Kruskal, On the shortest spanning tree of a graph and the travelling salesman problem, Proc. Amer. Math. Soc., 7, pp. 48–50, 1956.

S. Kumar, and H. Arora, K shortest paths and paths through R-specified edges in a protean network, ASOR Bulletin, Vol. 14, No. 2, pp. 3–8, 1995.

S. Kumar, E. Munapo, O. Ncube, C. Saguke, and P. Nyamugure, A minimum weight labelling method for determination of a shortest route in a non-directed network, Int J Syst. Assur. Eng. Manag. DOI 10.1007/s13198-012-0140-7, Springer, ISSN 0975-6809, Vol. 4, No. 1, pp. 13–18, 2013.

S. Kumar, E. Munapo, M. Leasoana, and P. Nyamugure, A minimum spanning tree approximation to the routing problem through ‘K’ specified nodes, Journal of Economics, Vol. 5, No. 3, pp. 307–312, 2014.

S. Kumar, E. Munapo, M. Leasoana, and P. Nyamugure, Is the travelling salesman problem actually NP Hard? Chapter 3 in Engineering and Technology, Recent Innovations and Research, Editor Ashok Mathani, International Research Publication House, ISBN 798-93-86138-06-4, pp. 37–58, 2016.

S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, A minimum spanning tree based approach to the travelling salesman tour, Opsearch, Vol. 55, No. 1, pp. 150–164, 2018a. {DOI: 10.1007/s12597-017-0318-5, pp. 1–15, 2017}.

S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, Some innovations in OR Methodology: Linear Optimization, Lambert Academic Publishing, ISBN: 978-613-7-38007-9, 2018b.

S. Kumar, E. Munapo, C. Sigauke, M. Al-Rabeeah, The minimum spanning tree with index

=2 is equivalent to the minimum travelling salesman tour, Chapter 8, Mathematics in Engineering Sciences: Novel Theories, Technologies and Applications, ISBN 9781351266321, Editor, Mange Ram, CRC Press (http://www.crcpress.com), pp. 227–243, 2019.

S. Kumar, E. Munapo, M. Lesaoana, and P. Nyamugure, P. Dickgale, Link-weight modification for network optimization: Is it a tool, philosophy, or an art? Chapter 11 in Recent Advances in Mathematics for Engineering, CRC Book, Ed. Mange Ram, CRC Press, (http://www.crcpress.com), pp. 227–243, 2020.

K. Mehlhorn, P. Sanders, Chapter 10: Shortest Paths, Algorithms and Data Structures: The Basic Toolbox. Springer. DOI: 10.1007/978-3-540-77978-0, ISBN 978-3-540-77977-2008.

E. Munapo, Development of a dummy guided formulation and exact solution method for TSP, Eastern European Journal of Enterprise Technologies, pp. 12–19, 2020.

E. Munapo, BC Jones, and S. Kumar, A minimum incoming weight label method and its application to CPM network, ORiON, Vol. 24, 2008, South African Journal of OR.

E. Munapo, S. Kumar, M. Lesaoana, and P. Nyamugure, A spanning-tree with node index

=2, ASOR Bulletin, Vol. 34, Issue 1, pp. 1–14, 2016. (www.asor.org.au).

E. Munapo, and S. Kumar, Linear Integer programming: Theory, Applications, Recent Developments, De Gruyter Publication, ISBN 978-3-11-070292-7, 2022.

R.M. Peart, R. Randolf, and T.E. Bartlet, The shortest route problem, Opns. Res., Vol. 8, pp. 866–868, 1960.

M. Pollack, and W. Weibenson, Solution of the shortest route problem – A review, Opns. Res., Vol. 8, pp. 224–230, 1960.

J.P. Saksena, and S. Kumar, The routing problem with ‘K’ specified nodes, Opns. Res., Vol. 14, No. 5, pp. 909–913, 1966.

S.M. Sinha, and C.P. Bajaj, The maximum capacity route through a set of specified nodes, Cahiers du Centre d’Etudes de Recherche Operationnelle, Vol. 11, pp. 133–138, 1969.

S.M. Sinha, and CP. Bajaj, The maximum capacity route through a set of specified nodes, Opsearch, Vol. 7, pp. 96–114, 1970.

F.B. Zhan, Three fastest shortest path algorithms on real road networks: Data structures and procedures, Journal of the Geographic Information and Decision Analysis, Vol. 1, No. 1, pp. 70–82, 1997.

Downloads

Published

2023-10-02

How to Cite

Kumar, S., Munapo, E., Nyamugure, P., & Tawanda, T. (2023). Minimum Spanning Tree Approach to Path Through K Specified Links. Journal of Graphic Era University, 11(02), 221–238. https://doi.org/10.13052/jgeu0975-1416.1127

Issue

2023: Vol 11 Iss 2

Section

Articles