Discover published sets by community

Explore tens of thousands of sets crafted by our community.

Categories

Computer Science

Algorithms

Network Flow Algorithms

Flashcards

0/4

Still learning

Edmonds-Karp Algorithm

An implementation of the Ford-Fulkerson method that uses the shortest augmenting path rule, resulting in a time complexity of $O(VE^2)$ , where $V$ is the number of vertices and $E$ is the number of edges.

Dinic's Algorithm

Dinic's algorithm solves the maximum flow problem using a level graph, which leads to an overall time complexity of $O(V^2E)$ in the worst case.

Push-Relabel Algorithm

The Push-Relabel algorithm determines the maximum flow in a flow network using preflow concept and relabeling the vertices. Its time complexity is $O(V^3)$ .

Ford-Fulkerson Algorithm

The Ford-Fulkerson algorithm solves the maximum flow problem by incrementally improving the flow along the paths. Time complexity, in worst case, is $O(Ef)$ , where $E$ is the number of edges and $f$ is the maximum flow in the network.

Know

Still learning

Click to flip

Know