Purchase Solution

Algorithm Problem

Not what you're looking for?

Ask Custom Question

Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e  E has capacity c(e) = 1. Assume also, for convenience, that |E| =  (V).

a. Suppose we implement the Ford-Fulkerson maximum-flow algorithm by using depth-first search to find augmenting paths in the residual graph. what is the worst-case running time of this algorithm on G?

b. Suppose a maximum flow for G has been computed, and a new edge with unit capacity is added to E. Describe how the maximum flow can be efficiently updated. (Note: It is not the value of the flow that must be updated, but the flow itself.) Analyze your algorithm.

c. Suppose a maximum flow for G has been computed, but an edge is now removed form E. Describe how the maximum flow can be efficiently updated. Analyze your algorithm.

See attached file for full problem description.

Attachments
Purchase this Solution

Solution Summary

Algorithm Problem is solved.

Solution Preview

Let G = (V, E) be a flow network with source s, sink t, and suppose each edge e  E has capacity c(e) = 1. Assume also, for convenience, that |E| =  (V).

a. Suppose we implement the Ford-Fulkerson maximum-flow algorithm by using depth-first search to find augmenting paths in the residual graph. what is the worst-case running time of this algorithm on G?
Answers:

The running time is: O(V E) because: the running time is O(E | f*|), and | f*| = O (V) because the flow is bounded by the capacity of any cut, and the capacity of the cut (s, V − s) is O(V ) because there are O(V ) edges leaving s, and ...

Purchase this Solution


Free BrainMass Quizzes
C++ Operators

This quiz tests a student's knowledge about C++ operators.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Basic Networking Questions

This quiz consists of some basic networking questions.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.