- 1-based implementation of 2-Satisfiability Problem (positive numbers for positive propositions and negative number for negative propositions.
- Note: Need to extract necesary code for each of the following subproblems.
- StronglyConnectedComponents
- BiconnectedComponents
- ArticulationPointsAndBridges
- This is uses Count Number of Spanning Trees and mint
- 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]
- Finds an eulerian path or a cycle in O(N)
- Maximum matching O(sqrt(V)*E)
- 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.
- 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.
- Can be a substitute of HungarianAlgorithm and also other MaxFlow with costs involved.
- 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.