Graph Theoretical Approaches To Solving Combinatorial Optimization Problems
Keywords:
Graph Coloring, Minimum Spanning Tree, Hamiltonian and Eulerian Graphs
Abstract
Combinatorial optimization problems play a crucial role in various fields such as logistics, network design, scheduling, and bioinformatics. Graph theory provides a structured approach to model and solve these problems efficiently. This paper explores key graph theoretical techniques for solving combinatorial optimization problems, including shortest path algorithms, maximum flow, minimum spanning tree, and graph coloring. We discuss their mathematical formulations, computational complexity, and real-world applications, emphasizing algorithmic strategies like Dijkstra’s algorithm, the Ford-Fulkerson method, and the Prim-Kruskal approach.
References
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press.
2. Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM.
3. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
4. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Mathematical Programming, 3(1), 233-245.
5. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
6. Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
7. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.
8. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
9. Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model. Physical Review E, 58(5), 5355.
10. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97.
11. Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1), 60-100.
12. Spielman, D. A., & Teng, S. H. (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 385-463.
2. Tarjan, R. E. (1983). Data Structures and Network Algorithms. SIAM.
3. Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice Hall.
4. Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Mathematical Programming, 3(1), 233-245.
5. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
6. Farhi, E., Goldstone, J., & Gutmann, S. (2014). A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028.
7. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8, 399-404.
8. Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman.
9. Kadowaki, T., & Nishimori, H. (1998). Quantum annealing in the transverse Ising model. Physical Review E, 58(5), 5355.
10. Kuhn, H. W. (1955). The Hungarian method for the assignment problem. Naval Research Logistics Quarterly, 2(1-2), 83-97.
11. Padberg, M., & Rinaldi, G. (1991). A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Review, 33(1), 60-100.
12. Spielman, D. A., & Teng, S. H. (2004). Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3), 385-463.
Published
2024-12-07
How to Cite
Bijumon Ramalayathil, & Aneesh Kumar K. (2024). Graph Theoretical Approaches To Solving Combinatorial Optimization Problems. Revista Electronica De Veterinaria, 25(2), 1423-1425. https://doi.org/10.69980/redvet.v25i2.1825
Section
Articles
