For questions about networks that inhibit source and sink nodes and a notion of flow.

learn more… | top users | synonyms

1
vote
0answers
16 views

Max Flow - Changing the capacity of an edge

Let $G=(V,E)$ be a flow network from $s$ to $t$. I have a maximum flow $f\colon E\to Z$ that was calculated using Ford-Fulkerson. How can I efficiently update $f$ when I need to subtract the ...
1
vote
1answer
20 views

Reduction to a max flow problem from a sudoku like puzzle

Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares ...
-2
votes
0answers
20 views

Sending flow through a graph so that flow through each node is at most $f$

Given a graph $G$ with source $s$ and sink $t$, suppose we want to send $f$ units of flow from $s$ to $t$ such that at most $p$ units of flow are sent through each node. The edges have infinite ...
0
votes
0answers
20 views

Real world application of independent sets

Independent sets are closely related to dominating sets. What are the real world applications of independent sets? Correspond to the question: Real world application of dominating set?
0
votes
0answers
2 views

Graph Theory: What is the best kind of network centrality to use to determine flows? sources/sinks?

I am working on a medium-sized (80 vertices), cyclic, directed network with commodities being passed around between agents. Its actually stock market data. I would like to determine who of the ...
1
vote
0answers
13 views

Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
0
votes
0answers
25 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
0
votes
0answers
53 views

Formulating shortest path (and tractable graphical model MAP) as submodular minimization

I'm trying to view maximum a posterior inference in discrete graphical model as a submodular minimization. For example, the linear chain model can be solved efficiently by the Baum-Welch algorithm. ...
0
votes
1answer
17 views

Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
3
votes
0answers
103 views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
41 views

Books on Multi-Commodity Minimum Cost Flow Problems

I'm searching for books on Multi-Commodity Minimum Cost Flow Problems (MCMCF) with theoretical aspects (solvability, optimality conditions, similar statements like in the case of Min Cost Flow,...). ...
0
votes
1answer
40 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
29 views

Proving the congestion of a butterfly network.

In MIT's 6.042j course assignment 6. In problem 5, it is required to prove that a butterfly network has congestion of \sqrt{N}. If we have an 8-input butterfly network and let's assume that all of the ...
1
vote
1answer
53 views

Explain how to find a max $(s-t)$ flow in a network

Explain how to find a max $(s-t)$ flow in a network, where some vertices are assigned capacities giving the maximum flow that can pass through those vertices. and Illustrate this method on the ...
0
votes
1answer
18 views

verifying minimum capacity of cut

So I have a cut $(P,P')$ on some network and its capacity is $13$. Now I'm told to assume that the current flow on the network is the max flow, is the cut of minimum capacity? So far all we've ...
0
votes
0answers
16 views

Airport Networking Flow Problem

I've been studying some introductory network optimization, and I noticed an interesting problem about flight networks. Suppose there are four locations $A$, $B$, $C$, and $D$ hold. One can fly from ...
0
votes
0answers
13 views

Show that the feasible flow problem has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0.

Show that the feasible flow problem, discussed in Application 6.1 below, has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0. App 6.1: The feasible flow ...
0
votes
1answer
53 views

How many “cuts” does a flow network have?

Assuming a single source, single sink digraph with |V| vertices, including source s and sink t. How many “cuts” does a flow network have?
0
votes
0answers
11 views

Totally uni-modular matrix

I encountered the following matrix and am wondering whether it is totally uni-modular or not: $$\begin{bmatrix} A_{n\times m} & 0_{n\times m}\\ I_{n\times m} & I_{n\times m}\\ ...
0
votes
0answers
21 views

How to find the minimum cut of smallest size in a Graph using Ford Fulkerson

I read the explanation that we have to remove all the saturated edges and then perform BFS to find connected component of s, but this will in my opinion will return the same set of nodes as in the ...
0
votes
0answers
14 views

Deriving/Fitting Origin-Destination Matrix of Directed Graph Flow

Let me preface this by saying that my this area of Mathematics is not my specialty (so pardon me if this is an easy question that I just cannot articulate correctly). I am trying to find a way to ...
3
votes
1answer
107 views

A equivalent condtion for existence of feasible circulation

A circulation in a directed graph $D$ is a function $g:E(D)\rightarrow\mathbb{R}$ satisfying the conservation condition at every vertex. Let $l,u:E(D)\rightarrow \mathbb{R}^{+}_{0}$ be a lower and ...
0
votes
0answers
23 views

Problem on costructing flows in a network with multiple sources and sinks

Problem : Formulate and prove a theorem that gives necessary and sufficient conditions so that a network with multiple sources and sinks has a flow that simultaneously meets all prescribed demands ...
0
votes
0answers
30 views

Graph of Network-Flow Matrices

This matrix is total unimodular 1 1 1 -1 0 0 0 1 1 0 -1 0 0 0 1 0 0 -1 I've read that nearly all ...
0
votes
0answers
12 views

Identify arbitrer policy of a network component

I would like to identify the formula of the service rate of a network component ARB based on input and output rates of flows crossing it. For instance, I have several flows which cross several ...
0
votes
0answers
57 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
0answers
25 views

Complexity of the Dinic, Malhotra, Kumar and Maheshwari (DMKM) method

I'm asked to prove that the complexity of the DMKM method is $\mathcal{O}(m\cdot n^{\frac23})$ if all capacities in a network are equal to 1. I have no clue where to start, can anyone give me a hint? ...
0
votes
2answers
35 views

What are dynamic networks.

From my understanding, dynamic networks are similar to traditional models except that they function in continuous time and have edges and nodes that evolve over time? Is this a correct understanding? ...
0
votes
1answer
16 views

Why are dynamic networks probabilistic? [duplicate]

I have a only survey level background in network science but am interested in it. I was browsing wikipedia and read this page, (https://en.wikipedia.org/wiki/Dynamic_network_analysis.) In that ...
2
votes
0answers
43 views

Possible Paths in Pipe Network

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit i have to ...
1
vote
1answer
188 views

Show that splitting an edge in a flow network yields an equivalent network.

Need help with this question from my Intro to Algorithms book: Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge ...
1
vote
2answers
42 views

Transportation: Minimizing Cost

I am trying to solve this problem, but I have had no luck. I have tried to set this up in MS Excel, so I could use Solver to find the solution, but I don't really know how to form this problem. As far ...
0
votes
0answers
27 views

Find convex efficient columns in Matrix

Consider a path-incidence matrix $A$ of a graph, where vertices are e.g. machines, paths are alternative production paths for a given product and entries $a_{ij}$ denote the workcontent for machine ...
0
votes
1answer
91 views

Optimization problem in flight scheduling

I found this question here The question is I wrote the LP problem as this: Let $x_{ij}$ be the maximum no.of flights between city i and city j. Let $a_0$ be the artificial link and $x_0$ be the ...
2
votes
1answer
32 views

optimization network models

This is a question from Wane Winston 's Book. I don't understand how to do this. I tried to do it this way but it doesn't seem to work. Let $C_{ij}$ be the cost of using box of i $ i>=j$ Then ...
1
vote
0answers
29 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
1
vote
1answer
73 views

Find if there is a matrix that her sum of each column and row representing two vectors

We have two vectors: $(a_1,...,a_n),(b_1,...,b_m)$. We want to know if there is a matrix $M_{nm}$ that all its elements are from $\left\{0,1\right\}$ with this condition: The sum of all the elements ...
1
vote
1answer
85 views

Question about edge disjoint path

I'm studying about edge disjoint path. If there is 3 distinct vertices (u,v,w) in given Graph G = (V,E), Let there is u -> v has k (k>1) edge disjoint paths, and v -> w has k edge disjoint paths, ...
1
vote
1answer
120 views

Matching between $n$ men and $m$ women

There is a group of $n$ men and $m$ women, and there is a symmetric dating between them (between the men and the women). How can we find a match between the men and the women (depending to the ...
2
votes
1answer
74 views

Flow: how does it work?

How does flow work ? I don't understand what they did. For example, why in the edged marked by 3, in the solution it's written 1 ? Morover, a maximum flow is the number a flow or the then longest flow ...
2
votes
0answers
134 views

Jackson's theorem to optimize mean queue length of a traffic model

I am working on traffic signals for a city transport system. I modeled the city transport using a queuing network as shown in the following image Arrival rate of "A" cars from outside is S1 and ...
0
votes
0answers
143 views

Node potentials of minimum cost flow successive shortest path algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
1
vote
1answer
74 views

A cut is minimal iff forward arcs saturated and reverse arcs flowless

Let $G = (V,A)$ be a network with arc capacity function $c$ and let $f$ be a flow on $G$. An arc $(x,y) \in A$ is said to be saturated if $f(x,y) = c(x,y)$ and flowless if $f(x,y) = 0$. In Flows in ...
0
votes
0answers
18 views

How to prove $\operatorname{val}(f) = f^+(X)-f^-(X)$ in flow networks?

In flow networks, for any subset $X$, the $\operatorname{val}(f) = f^+(X) - f^-(X)$. What is this theorem called and how can I prove it? I know that $f^-(\mathrm{sink}) - ...
1
vote
0answers
12 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
0
votes
0answers
40 views

Max Flow Min Cut with a Twist Proof

Let G=(V,E) be an undirected graph with positive integer edge costs. Let the set of paths s-t paths be denoted by P. the set of s-t cuts is denoted by C. Prove by construction that: Find the minimum ...
0
votes
0answers
107 views

Proof of correctness of Bidirectional Dijkstra's algorithm.

Problem 4.52 Network flows Ahuja Magnanti & Orlin Bidirectional Dijkstra's algorithm (Helgason, Kennington, and Stewart [1988]). Show that the bidirectional shortest path algorithm described in ...
3
votes
1answer
790 views

Max flow min-cut after a change in edges of capacity 1

I have been asked the following question: Let G be an input graph to the max flow problem. Let (A, B) be a minimum capacity s−t cut in the graph. Suppose we add 1 to the capacity of every edge in the ...
3
votes
1answer
27 views

linear programming and flow network

Here is the problem: I have hard time understanding the problem , what does it mean by "conservation factors" and how to approach the problem using linear programming. For what I understand, if a ...
0
votes
1answer
83 views

Maximum Flow and Change it by Edges Capacity Products

Suppose we have a Directed Graph and each edges has a positive capacity. if C is a positive constant, i say, if we add or subtract C to all edges capacity, the maximum flow, changed, (maybe increase ...