Applications of Graph Theory in Network Optimization: Theory and Practice

Rajan Sehgal

doi:10.36676/mdmp.v1.i3.35

Authors

Rajan Sehgal Dept. of Mathematics, Faridabad, Haryana

DOI:

https://doi.org/10.36676/mdmp.v1.i3.35

Keywords:

Graph Theory, Network Optimization, Shortest Path Algorithms, Maximum Flow Problem

Abstract

Graph theory has become a fundamental tool in the field of network optimization, providing a robust framework for analyzing and improving network systems. the diverse applications of graph theory in optimizing various types of networks, including communication, transportation, and social networks. We begin by outlining the theoretical foundations of graph theory, focusing on key concepts such as graph connectivity, shortest paths, and network flows. practical applications, highlighting how graph-theoretic algorithms and models are employed to solve real-world optimization problems. For instance, we examine how Dijkstra’s and Bellman-Ford algorithms are used for efficient routing in communication networks, and how the Maximum Flow Problem and its solutions impact the design of transportation infrastructure. Additionally, we explore applications in social network analysis, where graph theory helps in understanding and enhancing connectivity and influence among individuals.

References

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications. Prentice Hall.

Barabási, A. L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512. https://doi.org/10.1126/science.286.5439.509

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). The MIT Press.

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271. https://doi.org/10.1007/BF01386390

Ford, L. R., & Fulkerson, D. R. (1956). Maximal flows through a network. Canadian Journal of Mathematics, 8, 399-404. https://doi.org/10.4153/CJM-1956-039-7

Frank, M., & Tardos, É. (1992). A strongly polynomial algorithm for the assignment problem. Combinatorica, 12(4), 357-368. https://doi.org/10.1007/BF02122622

Gibbons, A. (1985). Algorithms for graph theory. Cambridge University Press.

Kleinberg, J., & Tardos, É. (2006). Algorithm design. Pearson.

Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50. https://doi.org/10.1090/S0002-9939-1956-0078680-6

Miller, G. L., & Teng, S.-H. (1997). Separators, depth-first search, and dynamic programming. Journal of the ACM, 44(6), 1048-1078. https://doi.org/10.1145/265230.265233