Advances and Applications in Discrete Mathematics

The Advances and Applications in Discrete Mathematics is a prestigious peer-reviewed journal indexed in the Emerging Sources Citation Index (ESCI). It is dedicated to publishing original research articles in the field of discrete mathematics and combinatorics, including topics such as graphs, coding theory, and block design. The journal emphasizes efficient and powerful tools for real-world applications and welcomes expository articles that highlight current developments in the field.

Submit Article

A STUDY ON COMPLETE GRAPH TO FIND OPTIMAL SOLUTION USING DIFFERENT ALGORITHMS IN NETWORK ANALYSIS

Authors

  • K. Rama Thulasi
  • G. Shobhalatha

Keywords:

complete graph, maximum flow, critical path, shortest path, minimum spanning tree

DOI:

https://doi.org/10.17654/0974165825049

Abstract

The objective of the study is to present an overview of network analysis with a special focus on the construction and application of complete graphs in organizational networks. Network analysis is approached both statistically and algorithmically to understand the relationships among system components. In this context, complete graphs allow for the effective implementation of various algorithms to solve the critical path, minimum spanning tree (MST), maximal flow and shortest route problems. These problems are addressed using different classical graph theory techniques such as the PERT (Program Evaluation and Review Technique) method to solve the critical path, Prim’s algorithm for finding the MST, the Ford-Fulkerson algorithm for computing the maximum flow in a network, and the traveling salesman algorithm for determining the shortest route of a complete graph  with n vertices in a single network design with an appropriate numerical example. The comprehensive connectivity in complete graphs ensures greater flexibility and accuracy in solving complex network-related problems in organizational and operational settings.

Received: June 24, 2025
Accepted: September 20, 2025

References

[1] F. Barnes and F. Harary, Graph theory in network analysis, Social Networks 5(2) (1983), 235-244. DOI: 10.1016/0378-8733(83)90026-6.

[2] A. Charnes and W. Cooper, Some network characterization for mathematical programming and accounting applications to planning and control, The Accounting Review 42(3) (1967), 24-52.

[3] D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, Addison-Wesley Publishing Company, Reading, MA, 1968.

[4] M. Nakomari, A note on the optimality of some all-shortest-path algorithms, Journal Operations Research Society of Japan 15(4) (1972).

[5] G. Charan Kumar and G. Shobhalatha, An empirical study on shortest path for graph clustering in network analysis, Journal of Physics: Conference Series 1344 (2019), 012043.

[6] X. C. Liang, Application of minimum spanning tree in network design, Journal of Suzhou Education Institute 2 (2008), 150-154.

[7] M. T. Kyi and L. L. Naing, Application of Ford-Fulkerson algorithm to maximum flow in water distribution pipeline network, International Journal of Scientific and Research Publications 8 (2018).

[8] S. Saha Ray, Graph Theory with Algorithms and its Applications in Applied Science and Technology, Springer India, 2013.

[9] Z. Jiang, X. Hu and S. Gao, A Parallel Ford-Fulkerson Algorithm for Maximum Flow Problem, WorldComp Proceedings, 2013.

[10] L. R. Ford Jr. and D. R. Fulkerson, Maximal Flow Through a Network, Rand Corporation, Santa Monica, CA, 1955.

[11] M. Shokry, New operators on Ford-Fulkerson algorithm, IOSR Journal of Mathematics (IOSR-JM) 11(2) (2015), 58-67.

[12] O. M. Alsalami and A. M. A. Rushdi, A review of flow-capacitated networks algorithms, techniques and applications, Asian Journal of Research in Computer Science 7(3) (2021), 1-33. Article no. AJRCOS.66089.

[13] H. M. Li, Q. Y. Xia and X. Wang, Research and improvement of Kruskal algorithm, Journal of Computer and Communications 5 (2017), 63-69.

[14] R. B. Angus and N. A. Gunderson, Planning, Performing, and Controlling Projects - Principles and Applications, Prentice-Hall, London, 1997.

[15] A. Sarswathi and S. Mahalakshmi, A new approach for solving the minimal flow, shortest route, maximal flow and the critical path, International Journal of System Design and Information Processing 12(1) (2024), 1-14.

[16] K. B. Bagshaw, NEW PERT and CPM in project management with practical examples, American Journal of Operations Research 11 (2021), 215-226.

[17] S. Singh, Project management and strategic objectives of the organization, Universal Journal of Industrial and Business Management 5 (2017), 10-11.

DOI: 10.13189/ujibm.2017.050102.

[18] O. K. Bodunwa and J. O. Makinde, Application of Critical Path Method (CPM) and Project Evaluation Review Techniques (PERT) in project planning and scheduling, Journal of Mathematics and Statistical Science 6(1) (2020), 1-8.

[19] K. G. Charles, Prim’s algorithm and its applications in the design of university LAN network, International Journal of Advance Research in Computer Science Management Studies 3(10) (2015), 131-136.

[20] C. Dahiya and S. Sangwan, Literature review on travelling salesman problem, International Journal of Research 5(16) (2018), 1152-1155.

[21] G. Reinelt, The Traveling Salesman: Computational Solutions for TSP Applications, Springer-Verlag, 1994. DOI: 10.1007/3-540-48661-5.

Downloads

Published

2025-10-11

Issue

Vol. 42 No. 8 (2025)

Section

Articles

License

Copyright (c) 2025 PUSHPA PUBLISHING HOUSE, PRAYAGRAJ, INDIA

Creative Commons License

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

_________________________

Licensing Terms:

Attribution: Credit Pushpa Publishing House as the original publisher, including title and author(s) if applicable.

Contact Pushpa Publishing House for more info or permissions.

How to Cite

A STUDY ON COMPLETE GRAPH TO FIND OPTIMAL SOLUTION USING DIFFERENT ALGORITHMS IN NETWORK ANALYSIS. (2025). Advances and Applications in Discrete Mathematics, 42(8), 773-786. https://doi.org/10.17654/0974165825049

Similar Articles

1-10 of 170

You may also start an advanced similarity search for this article.