Network Flow

Which of the following statements is true when comparing the Ford-Fulkerson algorithm and the Push-Relabel algorithm for solving maximum flow problems in networks?

A) The Ford-Fulkerson algorithm is a specific implementation of the Push-Relabel algorithm.

B) The Ford-Fulkerson algorithm always terminates in polynomial time for any network.

C) The Push-Relabel algorithm is a more efficient and faster alternative to the Ford-Fulkerson algorithm. 

D) Both the Ford-Fulkerson and Push-Relabel algorithms can find the maximum flow in a network, but the Push-Relabel algorithm garantees a shorter runtime.

E) None of the above.


Original idea by: Arthur Hendricks.

Comments

  1. Joao MeidanisJune 10, 2023 at 1:50 AM

    Interesting question, but it bothers me that you refer to Ford-Fulkerson and Push-Relabel as 'algorithms', when they are actually families of algorithms. Therefore, the question is a bit confusing and I prefer to drop it.

    ReplyDelete

Post a Comment

Popular posts from this blog

Networks and Graphs - Random Graphs

Random graphs are a type of mathematical object used to model complex systems, such as social networks on the internet. In a random graph with n vertices and edge probability p, the typical distance between two  vertices  follows a known property called small world phenomena which implies that: A) The distances between all pairs of vertices will be the same. B) The distances between vertices will follow a normal distribution. C) The distances between vertices will be roughly proportional to log(n). D) The distances between vertices will be randomly distributed. E) None of the above. Original idea by: Arthur Hendricks.
Read more