Graph Theory

1. Graph Theoretical Problems and Algorithms
   1. Shortest Path Problems
      1. Single Source Shortest Path
         1. Dijkstra's Algorithm
            1. Priority Queue Implementation
            2. Limitations with Negative Weights
         2. Bellman-Ford Algorithm
            1. Handling Negative Weights
            2. Applications in Distance Vector Routing
      2. All-Pairs Shortest Path
         1. Floyd-Warshall Algorithm
            1. Dynamic Programming Approach
            2. Time Complexity Considerations
         2. Johnson's Algorithm
            1. Use of Bellman-Ford to Reweight Edges
            2. Combination with Dijkstra's Algorithm
   2. Network Flow Problems
      1. Maximum Flow
         1. Ford-Fulkerson Method
            1. Residual Graph Concept
            2. Augmenting Path Algorithm
         2. Edmonds-Karp Algorithm
            1. Breadth-First Search for Finding Paths
            2. Performance Improvements Over Ford-Fulkerson
         3. Dinic's Algorithm
            1. Blocking Flows and Layered Network Approach
            2. Analysis of Running Time
      2. Minimum Cost Flow
         1. Cycle Cancelling Method
         2. Successive Shortest Path Algorithm
         3. Capacity Scaling Approach
   3. Graph Coloring
      1. Chromatic Number
         1. Definition and Calculation
         2. Chromatic Polynomial
      2. Four Color Theorem
         1. Overview and Historic Context
         2. Applications in Map Coloring
      3. Greedy Coloring
         1. Approximation Techniques
         2. Heuristic Methods for Optimization
      4. Interval Graph Coloring
         1. Applications to Scheduling Problems
         2. Comparisons to Interval Covering Problems
   4. Graph Matching
      1. Maximum Matching
         1. Definition and Use Cases
         2. Hungarian Algorithm for Bipartite Graphs
      2. Bipartite Matching
         1. Hopcroft-Karp Algorithm
            1. Complexity Analysis
            2. Implementation Details
         2. Applications to Real-World Problems
      3. General Graph Matching
         1. Blossoms and Edmonds' Matching Algorithm
         2. Perfect Matching in Complete Graphs
   5. Covering and Partitioning
      1. Vertex Cover
         1. Approximation Algorithms
         2. Applications in Resource Allocation
      2. Edge Cover
         1. Exact Algorithms
         2. Relationship with Matching
      3. Graph Partitioning
         1. Use in Load Balancing
         2. Kernighan-Lin Algorithm
         3. Multi-Level Partitioning Strategies
   6. Other Graph Problems
      1. Traveling Salesman Problem (TSP)
         1. Variants: Metric TSP, Asymmetric TSP
         2. Approximation Strategies: Nearest Neighbor, Christofides’ Algorithm
      2. Hamiltonian Cycle Problem
         1. Backtracking and Branch-and-Bound Approaches
         2. Relation to TSP
      3. Minimum Cut Problem
         1. Stoer-Wagner Algorithm
         2. Relationship with Maximum Network Flow
      4. Graph Isomorphism Problem
         1. Canonical Form Approaches
         2. Applications and Current Challenges in Solving
   7. Algorithm Optimization and Complexity
      1. Use of Data Structures in Graph Algorithms
         1. Balanced Trees and Fibonacci Heaps for Dijkstra's Algorithm
         2. Disjoint Set Union for Kruskal’s Algorithm
      2. Analysis of Time and Space Complexity
         1. Trade-offs Between Different Algorithmic Approaches
         2. Real-World Performance Considerations
      3. Heuristic and Probabilistic Methods in Graph Algorithms
         1. Genetic Algorithms
         2. Simulated Annealing Techniques