A collection of advanced graph algorithms, data structures, and optimization projects developed for the Graph-Based Algorithms course.
Solving a dependency-based selection problem (Project Selection Problem) using flow networks.
- Dinic's Algorithm: High-performance Max-Flow implementation with Level Graphs and Pointer Optimization.
- Min-Cut Analysis: Using the Max-Flow Min-Cut theorem to find the optimal subset of resources (primes) that maximizes "luck" values vs. logarithmic costs.
Implementation of a linear-time algorithm for NP-hard problems in specialized graph classes.
-
Lex-BFS: Efficient partition refinement to find a Perfect Elimination Ordering (PEO) in
$O(V+E)$ . - Optimization: Finding the Maximum Weight Independent Set and its dual, the Minimum Weight Vertex Cover, using greedy dual-based approaches.
-
Lab 1: Union-Find (DSU) – Disjoint Set Union with Path Compression and Union by Rank (
$O(\alpha(n))$ complexity). - Lab 2: Shortest Paths – Implementation of Dijkstra (Priority Queue) and Bellman-Ford for negative cycles.
- Lab 3: Minimum Spanning Trees – Kruskal's and Prim's algorithms for network connectivity.
- Lab 4: Flow Basics – Foundations of residual networks and augmenting paths.
- Language: Python 3.x
- Juliet - juliet2112
Developed for the Graph Algorithms course at marcinlos.github.io/algograf/