Skip to content

Latest commit

 

History

History
37 lines (34 loc) · 2.3 KB

README.md

File metadata and controls

37 lines (34 loc) · 2.3 KB
Raw

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