The network-flow tag has no wiki summary.
1
vote
0answers
41 views
Which cut does the “minimum cut” refer to?
My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
2
votes
0answers
33 views
Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?
I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book.
Which does "cut" most commonly refer to?
p.s. I am aware that "cut" itself can be defined to ...
0
votes
1answer
28 views
Do “cut set” and “edge cut” mean the same thing?
The definitions I have are:
A cut set of a graph $G$ induced by a partition of $G$'s vertices
into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$
and another endpoint in ...
0
votes
0answers
14 views
Are there any subsets of the integer maximum flow problem for generalised networks which are solvable in polynomial time?
Are there any classes of generalised flow networks for which the integer maximum flow problem is solvable in polynomial time? By generalised flow network I mean a flow network where each edge has a ...
2
votes
0answers
56 views
Max - Flow and Min - Cut, Minimize the number of visible boxes
Suppose that you are given a set of boxes, with each box as a rectangular parallelepiped with side lengths as (i1, i2, i3). And each side length is between half a meter and one meter.
How should a ...
0
votes
0answers
30 views
Augmenting path results in max-flow polynomial
Explain why augmenting along shortest augmenting path results in polynomial algorithm for max-flow.
My idea is that it's somehow connected to creating the residual graph
along the augmenting ...
0
votes
0answers
23 views
Solving for Max Flow/Min Cut after Removal of Certain Nodes: is it Possible to Use Previous Information for the Next Step?
Given a certain directed graph, I would like to remove a set of nodes first, and then calculate the Max flow/Min Cut of the new system. After I would like to repeat over and over by removing a ...
0
votes
0answers
58 views
Using maximum flow algorithm to check existence of a matrix
Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given:
The maximum values of the row sums
The column sums
...
0
votes
0answers
29 views
Min cost flow problem with “time window” constraints
Are there any variants of the min cost network flow problem where the flow into/out of the demand nodes must happen within specific time intervals? I'm thinking of a model which would ideally ...
1
vote
0answers
80 views
Two-commodity minimum cost flow with antisymmetric costs
I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a ...
1
vote
0answers
64 views
planarity of graph as a consequence of its flow
Is it possible to distinguish planar and non-planar graphs (networks as a matter of fact) by flows? That is, is there a flow criterion for a graph being planar or not?
0
votes
2answers
55 views
what is the complexity and how to start
Every year, Prof Gupta assigns the instructors to various faculty committees. There
are n faculty members and c committees. Each committee member has submitted a list of
their prices for serving on ...
2
votes
1answer
170 views
Flow network - minimum capacity cuts proof
Let's start out by reviewing max-flow min-cut, as well as the flow networks they operate on.
http://en.wikipedia.org/wiki/Flow_network
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
Let $G = ...
0
votes
1answer
41 views
Individual components of flow along edges in a graph
I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an ...
2
votes
1answer
80 views
Unimodular matrix definition?
I'm a bit confused. Based on Wikipedia:
In mathematics, a unimodular matrix M is a square integer matrix
having determinant +1, 0 or −1. Equivalently, it is an integer matrix that is invertible ...
0
votes
1answer
75 views
Network Simplex Method: How to relabel the vertices and arcs such that the truncated matrix is upper triangular and non-singular.
Suppose $G = (V, A)$ is the acyclic weakly connected digraph with$ V $consisting of vertices $v_{i}$ $(i = 1, 2, ..., 8)$ in which the seven arcs are $(v 1 , v 2 ), (v 3 , v 2 ), (v 4 , v 3 ),(v 7 , v ...
0
votes
1answer
164 views
Network flow: Why is min-cut determined by unsaturated edges?
Suppose we have an oriented graph and max-flow has been determined.
I found that to determine min-cut or minimum s-t cut can then be found by labeling graph nodes such that nodes belonging to source ...
0
votes
1answer
284 views
Network Flow Problem - How to solve with a matrix?
Find the general flow pattern of the network. Assuming that the flows are all nonnegative, what is the smallest possible value for $x_4$?
Points of Intersection: Flow In = Flow Out
A: $x_1+x_4 = ...
1
vote
1answer
101 views
Max flow in a flow network such that $e \in E$ has the maximum flow it can have.
Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among ...
3
votes
2answers
306 views
What's an intuitive explanation of the max-flow min-cut theorem?
I'm about to read the proof of the max-flow min-cut theorem that helps solve the maximum network flow problem. Could someone please suggest an intuitive way to understand the theorem?
3
votes
2answers
256 views
maximum flow ford-fulkerson analysis
I am reading about maximum flows in Introduction to algorithms by Cormen etc.
Ford-Fulkerson algorithm is given below.
FORD-FULKERSON(G, s, t)
...
2
votes
1answer
271 views
Min-cut Max-flow $\Rightarrow$ Dilworth's theorem
Dilworth's theorem states that given a finite partially ordered set, the length of the maximal anti-chain, is equal to the minimal number of chains needed to partition the set.
I need to prove that ...
3
votes
1answer
185 views
Does the greedy method guarantee max flow in a directed tree?
Consider a directed tree $G$ with a root node $s$. Let $s$ be the source node of $G$ and its leaves the sink nodes (call these leaves $t$). (And of course edges have their respective capacities like ...
9
votes
4answers
398 views
Probability of global epidemic
Consider $\mathbb{Z}^2$ as a graph, where each node has four neighbours. 4 signals are emitted from $(0,0)$ in each of four directions (1 per direction) . A node that receives one signal (or more) at ...
4
votes
1answer
868 views
Min cut Max flow - Finding the cut with least vertices
Suppose a network $N = (G,c,s,t)$ where $c$ is real.
How do you find all min-cuts? (or how do you find the cut with the least number of vertices)
I've tried messing with the capacity, but since it ...
2
votes
0answers
78 views
Maximum Flow in Dynamic graphs
I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in $G$ now new node added/deleted with related ...
0
votes
1answer
227 views
Multicommodity flow in polynomial size
The original linear program for multicommodity flow has exponentially many variables. How to find equivalent linear program that has polynomial size?
Linear program of multicommodity flow
$maximize ...
0
votes
2answers
373 views
How to calculate the maximum flow in this graph by the Edmonds-Karp algorithm?
How do I use the Edmonds-Karp algorithm to calculate the maximum flow? I don't understand this algorithm $100\%$. What I need to know is about flow with minus arrow. Here is my graph:
.
Our ...
1
vote
1answer
62 views
Does the sparsest cut always have a solution?
How do I prove that the sparsest cut always has an optimal solution which is the cut for some vertex-subset?
It looks like it should be a kind of fundamental theorem for sparsest cut. But I didn't ...
0
votes
2answers
158 views
The flow/cut gap theorem for multicommodity flow
Let's start out by reviewing very popular max-flow min-cut theorem
Max-flow min-cut theorem:
The maximum value of an $s-t$ flow is equal to the minimum capacity of an $s-t$ cut.
For ...
2
votes
1answer
99 views
Sparsest cut is solvable on trees
The problem is to prove that Sparsest cut is solvable on trees in polynomial time.
A short review, a sparsest cut is linear program
$$\min \frac{c(S,\overline{S})}{D(S,\overline{S})}$$
where ...
4
votes
1answer
114 views
Book on advanced topics of Network Flows
I am taking linear optimization class. Could you suggest me good fundamental textbook on advanced topics of network flows. To be more specific I am interested in: Multicommodity flow and multicut, the ...
1
vote
0answers
137 views
Graph closure problem [closed]
In graph theory exist the closure problem. In particular the maximum closure problem a directed graph $G = (V, A)$ with vertex weights $w_i$ is given and we want to find a closed subset of vertices ...
2
votes
1answer
462 views
Linear Algebra: Network Flow problem
So I have the following problem:
And I have obtained the following system of equations:
$$\begin{align*}
-x_1+x_2&=400\\
x_1+x_3-x_4&=600\\
x_2+x_3+x_5&=300\\
x_4+x_5&=100
...
0
votes
1answer
74 views
3
votes
1answer
248 views
Construct dual network for conversion of min-cut problem to shortest path problem
I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...
3
votes
1answer
231 views
network flow as a linear combination
How would I write the flow of the following graph as a linear combination of flows along s,t-paths and t,s-paths and cycles? The values of the edges in the graph represent the flow along that edge.
...
1
vote
1answer
374 views
What is the restriction matrix used for in the stepping stone method?
Let's say that we want to solve a classic transportation problem without capacities using the stepping stone method. (Problem definition: A bipartite graph with supply nodes a1...m, demand nodes ...
2
votes
2answers
400 views
Solving project selection with a network flow algorithm
I am currently studying network flow algorithms and one of its application is supposed to be "Project Selection". A (more) complete description is given here, but the problem basically is this:
There ...
6
votes
3answers
256 views
What sort of mathematical methods and models are used to model the brain
What sorts of mathematical tools, models and methods and theoretical frameworks do people use to simulate the function of the brain's neural networks? What mathematical properties do different brains ...
2
votes
1answer
271 views
Queueing Theory: How to estimate steady-state queue length for single queue, N servers?
I have a real-life situation that can be solved using Queueing Theory.
This should be easy for someone in the field. Any pointers would be appreciated.
Scenario:
There is a single Queue and N ...
1
vote
1answer
137 views
calculating walks in an undirected graph using linear algebra identity
I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says:
Walks: which allow both nodes and
edges to be ...
2
votes
1answer
385 views
Convert capacitated network flow problem
Assume a capacitated network flow problem with graph $G = (N,A)$ and capacities $u_{ij}$ (finite), costs for each path of $c_{ij}$ and I/O of $b_{i}$.
How can it be shown there is an equivalent ...
