The network-flow tag has no wiki summary.
4
votes
0answers
48 views
Understanding Dinic's algorithm using dynamic trees
I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan ...
2
votes
1answer
65 views
Finding paths from the result of max flow
Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That ...
2
votes
2answers
70 views
State machine with knowledge of prior states?
I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.
Below is an example graph ...
2
votes
1answer
56 views
Multicommodity circulation formulation
On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
2
votes
0answers
78 views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are ...
0
votes
1answer
56 views
In flow networks, may source/sink have incoming/outgoing edges?
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?
Flow-networks are always pictures with no ...
2
votes
1answer
192 views
Maximum number of augmenting paths in a network flow
Let's say we a have flow network with $m$ edges and integer capacities.
Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow.
A good way to start thinking ...
11
votes
2answers
164 views
Are link-cut trees ever used in practice, for max flow computation or other applications?
Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as ...
0
votes
1answer
86 views
Push relabel algorithms in flow networks
In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -
$$
\sum_{u \in U}e(u) \;=\;
\sum_{u ...
5
votes
3answers
152 views
XOR-like behavior in flow networks
XOR is not the correct name, but I am looking for some kind of exclusive behavior.
I am currently solving a set of different (assignment) problems by modeling flow networks and running a ...
3
votes
0answers
358 views
Remove minimum number of vertices to disconnect the graph
Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.
My intuition tells me ...
2
votes
1answer
132 views
2OPT Approximation Algorithm for Multiway Cut Problem
In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum
set of edges in $E$ whose removal ...
6
votes
2answers
731 views
Finding negative cycles for cycle-canceling algorithm
I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is ...
-2
votes
1answer
193 views
Dijskstra's algorithm, maximum flow
For directed graph $(G=(V, E),s,t,{Ce})$ in which we want to maximize max flow. All edge capacities are at least one. Define the capacity of an $s \to t$ path to be the smallest capacities of ...
5
votes
0answers
233 views
A variation in Ford-Fulkerson algorithm
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.
I was thinking that when we augment a ...
8
votes
2answers
1k views
Maximum Independent Set of a Bipartite Graph
I'm trying to find the Maximum Independent Set of a Biparite Graph.
I found this in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":
Problem:
...
2
votes
1answer
147 views
Reason for global update steps in the push-relabel algorithm
I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?
7
votes
1answer
191 views
CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof
In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| ...
5
votes
1answer
163 views
Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?
We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
7
votes
2answers
1k views
Reducing minimum vertex cover in a bipartite graph to maximum flow
Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim ...
3
votes
2answers
292 views
Finding the maximum bandwidth along a single path in a network
I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link ...
