README

My personal algorithmic libraries

Index

• Graph
  • 2-SAT:
    • 1-based implementation of 2-Satisfiability Problem (positive numbers for positive propositions and negative number for negative propositions.
  • Connected Components
    • Note: Need to extract necesary code for each of the following subproblems.
    • StronglyConnectedComponents
    • BiconnectedComponents
    • ArticulationPointsAndBridges
  • Count Number of Minimum Spanning Trees
    • This is uses Count Number of Spanning Trees and mint
  • Count Number of Spanning Trees
    • Note: Code is equivalent to building the matrix with addEdge and finding determinant. mint is just a ModularInt with the defined operations (/, *, +, -) [note modular division needed]
  • Eulerian Path And Cycle
    • Finds an eulerian path or a cycle in O(N)
  • HopcroftCarp.cpp
    • Maximum matching O(sqrt(V)*E)
  • Hungarian Algorithm
    • Finds a weighted maximum matching in O(V^3) best for dense graphs, for non complete graphs use INF as edge cost, an alternative is to run MinCostMaxFlow.
  • MaxFlow
    • Has a running time of O(|V|^2 |E|).
    • Can be used to find MaximumMatching and runs relatively fast, in theory same complexity as HopcroftCarp if all edges has capacity 1.
  • MinCostMaxFlow
    • Can be a substitute of HungarianAlgorithm and also other MaxFlow with costs involved.
  • VertextCover
    • Can find a minimum vertex cover after a maximum matching is provided.
    • NOTE: It does not have MaxMatching you have to run MaxMatching and then pass the matching to this algorithm.
• Dynamic Programming
• Math
• Trees
• String
• Geometry