Considers the following characteristics of algorithms that find the maximum flow in a flow network:
- Uses a combination of BFS and DFS;
- Uses BFS to find the shortest augmenting path (in terms of number of edges used);
- Finds augmenting paths in an unspecified manner;
- Maintains a "preflow" instead of finding augmenting paths.
Which algorithms below fit these characteristics, respectively?
- Ford-Fulkerson, Edmonds-Karp, Dinitz, Push-Relabel;
- Dinitz, Ford-Fulkerson, Edmonds-Karp, Push-Relabel;
- Dinitz, Edmonds-Karp, Ford-Fulkerson, Push-Relabel;
- Push-Relabel, Edmonds-Karp, Ford-Fulkerson, Dinitz;
- None of the above.
Original idea by: Filipe Roberto.
No comments:
Post a Comment