Skip to main content

Questions tagged [network-flow]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
15 views

Maxflow-mincut implies Menger (vertices)

I was studying graph theory when a question came to my mind. I am trying to understand a proof of the Menger's theorem (vertex version) using the maxflow-mincut (capacity on vertices). I think I miss ...
Amanda Wealth's user avatar
1 vote
0 answers
27 views

Braess paradox: a network counterintuitive NE graph example

I cannot understand here why switching to $CD$ is a dominant strategy?? If $x>4500$ then it may be beneficial for a Nash-Equilibrium to go from $C$ to $B$ and not from $C$ to $D$. And hence $CD$ is ...
user122424's user avatar
  • 3,936
0 votes
0 answers
8 views

Finding a network such that two slight modifications of Edmond-Karp output different flows

Let $\mathcal{N} = (V, E, c)$ a network where $c$ is a function that maps edges to values in $\mathbb{R}^{+} \cup \{0\}$. Let $\Gamma^{+}(x) = \{y \in V : (x, y) \in E\}$ and $\Gamma^{-}(x) = \{y \in ...
lafinur's user avatar
  • 3,354
1 vote
1 answer
47 views

How does making a spanning tree solution "strongly feasible" for the Network Simplex method assist in cycling prevention?

Question: How does making a spanning tree solution "strongly feasible" for the Network Simplex method assist in cycling prevention? To start, I was reading An Implementation of Network ...
Miss Mae's user avatar
  • 1,687
0 votes
0 answers
21 views

Does Flow Networks in Graph Theory includes latency or is it another model?

I studied graph theory at the university but "flow networks" were outside the course topics. While reading material about flow networks it is not clear for me if the latency concept (beyond ...
sw.'s user avatar
  • 101
1 vote
1 answer
37 views

How many integer $k$-flows (which are allowed to be zero)?

Consider a graph $G=(V,E)$. An integer $k$-flow is a map $\phi: E \to \mathbb{Z}$ such that $|\phi(e)| < k$ and on each site, the sum of $\phi$ on incoming edges equals that on outgoing edges (this ...
John Donne's user avatar
0 votes
0 answers
76 views

Finding a minimum s-t cut with the smallest number of edges in a directed graph

Given a directed graph $G = (V, E)$ and integer edge capacities $u(e)$, $e \in E$, you wish to find, among all minimum $s$-$t$ cuts, one that contains the smallest number of edges. Show how you can ...
Nico Konrad's user avatar
0 votes
0 answers
25 views

Fair Bandwidth Allocation

This is a question that sounds simple but I can't figure out a proper solution. The question is as follows. Say you have a binary tree of 3 levels(8 leaves). Let's say this represents a network where ...
oshan yalegama's user avatar
0 votes
1 answer
46 views

Graph problem regarding Max-Flow Min-Cut while modifying capacity of an edge

Ok so i have the following problem, which is based on the Max Flow Min Cut Theorem: Let $R = (G, s, t, c)$ be a transportation network, where $c : E(G) → Z^{∗}_{ +}$. Consider $e = uv ∈ E$ and $p ∈ Z$....
Sparrow's user avatar
  • 13
1 vote
0 answers
58 views

Having a maximum flow in a transportation network, find the maximum flow for the same network if exactly 1 edge changes its capacity. [closed]

I have an idea for the c) problem, finding an augmenting path from network R to network R1, and then applying the same procedure until i get the maximum flow for Rp, its similar to what Ford_Fulkerson ...
Denis Loghin's user avatar
3 votes
1 answer
99 views

Maximum cost flow in acyclic tournament

Given a digraph with vertices numbered from $1$ to $n$, where the edge $(i,j)$ exists if and only if $i<j$, which is called an “acyclic tournament with order $n$”. The problem is to find the ...
Alex-Github-Programmer's user avatar
0 votes
1 answer
85 views

Divide vertices of undirected graph to two groups by minimum number of edges

Assume I have an undirected, connected graph G(V,E). I want to find an algorithm that divides the vertices in V to two groups by the goal: minimum number of edges connecting between the two groups. ...
MrTuna's user avatar
  • 3
0 votes
0 answers
52 views

Network flow - does edge lie on directed path

a) Let $f$ be a flow network $(G, c, s, t)$ and $e$ an edge such that $f(e) > 0$. Then there must exist a directed path from $s$ to $t$ that contains the edge $e$. b) Let $f$ be a flow network $(G, ...
popcorn's user avatar
  • 311
1 vote
0 answers
93 views

Combinatorial Optimization William Cook et al

I'm working on exercises from Combinatorial Optimization by Cook et al. and I'm a little stuck on how to proceed with the following problem: Given digraph $G, u\in \textbf{R}^E$, and $r,s\in V$, find $...
Anthony Kulick's user avatar
0 votes
0 answers
27 views

How to reduce a problem to feasible circulation/network flow, in the case of cyclic dependency

Background: Given a set of vertices and conditions, in order to see if all the conditions can be met, I want to reduce it to a circulation problem such that all the conditions in the original problem ...
punypaw's user avatar
  • 465
0 votes
0 answers
10 views

1D vs 2D transition rates between ODE variables could perhaps relate to 'network flow'?

1D vs 2D transition schemes (The linked picture should be very helpful in understanding this question!) I am working on a population model using ordinary differential equations. I have a 1D system ...
Dan Byrom's user avatar
0 votes
0 answers
23 views

Number of Iterations to maximize flow given recurrence relation

I have proven that there is always an augmenting path of capacity at least $\frac{F}{|E|}$. How do I use this to bound the number of rounds given that I use a relation to increase the flow by a ...
Money Mit's user avatar
0 votes
0 answers
37 views

Firefighter problem - finding min-cut in capacitated network (Help)

As my final project my colleagues and I chose to research the firefighter problem. We could really use your help in the section of MIN-BUDGET regarding the DirlayNet (Directed layered network) ...
Shaggy's user avatar
  • 1
-1 votes
1 answer
131 views

Giving an upper bound on the length of any augmenting path G'

Let $G = (V, E)$ be a bipartite graph with vertex partition $V = L∪R$, and let $G'$ be its corresponding flow network. Give a good upper bound on the length of any augmenting path found in $G'$ during ...
Lucy123's user avatar
  • 11
0 votes
0 answers
48 views

Minimal number of edges in G that must be removed to separate two nodes.

This is the question I am trying to answer: Let $G = (V,E)$ be a directed graph and $s,t$ $\epsilon$ $V$ with $s$ $\neq$ $t$, prove that the minimal number of edges in G that must be removed in order ...
Sulla's user avatar
  • 11
0 votes
0 answers
33 views

Minimum Spanning Trees problem with multiple roots

I'm looking for algorithms that handle the minimum spanning tree problem on connected graph with multiple roots. In other words, the resultant trees are radial graphs. Thank you in advance.
Goga's user avatar
  • 21
1 vote
0 answers
39 views

What is the name of this type of network flow problem?

I encountered a specific type of network flow problem, and I want to know if this type of problem has already been studied before. However, I have been unable to find relevant literature because I don'...
Bosnicht's user avatar
0 votes
0 answers
16 views

Guaranteeing Integer Maximum Flow in Networks?

Let N = (V,A,c,s,t) be a network. Assuming that all minimum s-t cuts in N consist only of edges with integer capacities, then there is an integer maximum flow in N. I think this should be true because ...
stilllearning's user avatar
8 votes
2 answers
237 views

Land-based path from top to bottom if and only if no water based path from left to right

We are given a $M \times N$ grid where each tile is either a land or water tile. We may move from a land tile to any other land tile that is orthogonally adjacent to the current land tile. We may move ...
user308485's user avatar
  • 1,279
0 votes
0 answers
18 views

An Equivalence condition for $u,v$- node cut (or $u,v$-separator)

How can prove the only if part of the following property. It seems easy, but I can not find a proof. Given $U\subseteq V$ and a nonadjacent pair of nodes $u, v\in U$, there exists a path in $G(U)$ ...
zjdxsmjd's user avatar
0 votes
0 answers
28 views

Minimizing complex system of equations (maxflow or linear programming possible?). Help Needed.

I have a set of groups $G$. Each group $G_i$ is composed of values $[g_{i0}...g_{ij}]$ where $g_{ij} \in \mathbb{R}$ . I also have a set of values $C_0 ... C_k$ where $C_k \in \mathbb{R}$. In this ...
pureleaf1234's user avatar
2 votes
0 answers
63 views

Distance/Similarity between two paths in a network

I have a weighted directed graph representing the intensity of movements of individuals between locations, with weights representing the mobility flow. I have another dataset consisting of particular ...
David Young's user avatar
0 votes
1 answer
50 views

Converting between shortest path problems

Given a weighted digraph $G$, and collections of vertices $R, S \subset V$ , consider the problem of finding a shortest length path joining a vertex $r\in R$ to a vertex $s\in S$. Reduce this to the ...
Maths Owl's user avatar
1 vote
1 answer
185 views

MILP constraints for connectivity in a subgraph

I have an MILP problem where I have to choose a set of vertices 'm' from complete set of vertices such that all the 'm' vertices are connected. Assume there are a set of vertices numbered 1...n. Out ...
DKumar's user avatar
  • 13
0 votes
1 answer
59 views

Forbid Flow to Split in Flow Network

Is it possible to somehow assert that flows are not allowed to split in flow networks by design? Assume you have a sink $s$ and a incoming flow value of 10. Furthermore you have 3 nodes $v_1, v_2, v_3$...
Dom's user avatar
  • 19
-2 votes
1 answer
43 views

question about flow decomposition theorem

Given a flow network on a directed graph, the flow decomposition theorem tells us that it can be composed into a finite set of s-t paths and cycles. I have two questions about the flow decomposition ...
cbyh's user avatar
  • 535
0 votes
0 answers
46 views

Use maxflow to change edge capacities for higher max flow

Suppose we're given the max-flow and the corresponding residual graph, and edge capacities for an arbitrary digraph. We're also given said graph. Is there a way to check in linear time whether there ...
tquinn's user avatar
  • 31
0 votes
0 answers
76 views

Practical difference between definitions of flow?

This answer describes two different definitions of network flow. I'm unable to understand if there's a functional difference between the two. In which minimal cases do the definitions not align for ...
aome's user avatar
  • 103
0 votes
1 answer
33 views

What do two opposing arrows mean in a network flow context

I came across a question with notation like this: $G$ does not contain any subgraph of the form $v^→_← w$. I think this means that there is no way to push flow from v to w. Given this is a bipartite ...
aome's user avatar
  • 103
0 votes
1 answer
97 views

Does there exist a “Klee-Minty variant” for the Network Simplex method?

The Network Simplex method works much faster than the traditional Simplex method for min/max flow problems. However, the Simplex algorithm struggles to handle the Klee-Minty cube because most pivoting ...
Miss Mae's user avatar
  • 1,687
1 vote
0 answers
41 views

What do you call a matrix that has rows and columns of similar index summing up to same numbers?

I'm building a flow matrix of a graph and I came to realize that my matrix of size $ N \times N $ has this simple property: $$ \sum_{n=1}^{N}{A_{ni} } = \sum_{n=1}^{N}{A_{in} } $$ for $ i \in [1, N] $....
Alex's user avatar
  • 11
0 votes
1 answer
73 views

How to find the reduced cost of a variable in a large data set

I have been given a large data set with a list of starting nodes, their destination nodes, and the length to each destination node from each starting node. Using Dijkstra's algorithm, I coded a ...
Housefire's user avatar
  • 432
0 votes
1 answer
55 views

Pouring bottles into buckets but not too much: how to configure Maximum Flow with Lower Bounds to solve this assignment problem?

Problem $n$ jars of water with different volumes $v_i$ have to be assigned to $m$ empty buckets with different volumes $V_j$ $n \ge m$. A jar can only be poured into 1 bucket. Multiple jars can be ...
WaterFox's user avatar
  • 139
2 votes
1 answer
105 views

Scheduling jobs with fixed start and end time on limited machines

The problem: Given n jobs with fixed start and end times, and k machines each capable of doing only one job at a time, find if it is possible to schedule all n jobs on these k machines using network-...
user3917631's user avatar
1 vote
0 answers
49 views

Prove that if the residual graph doesn't contain a path from $u$ to $v$, then $e=(u,v)$ crosses some minimum cut

Prove: given a flow network $N=(G,s,t,c)$ with a maximum flow $f^*$ and a given edge $e=(u,v)$, then there's no path from $u$ to $v$ in $N_{f^*}$. I've seen this thread, but the only answer there is ...
sadcat_1's user avatar
  • 249
0 votes
1 answer
52 views

Maximum Flow with recursive, dynamic weights

I am looking for an algorithm that functions similarly to the maximum flow algorithm. The only difference is that each edges weight changes according to the weight that it was traversed before, and ...
DaveTheAl's user avatar
  • 123
1 vote
1 answer
64 views

Do all Wardrop Equilibria have the same social cost?

I'm currently studying non-atomic congestion games, and i've come accross the following definition of the price of anarchy: Let $f$ be a Wardrop equilibrium and let $f^*$ be a system optimal flow. ...
George Moneftsis's user avatar
2 votes
1 answer
202 views

How to configure Minimum Cost Maximum Flow to solve Unbalanced Assignment Problem?

Problem $n$ objects have to be assigned to $m$ categories, with $n \ge m$. Assigning an object $i \in [n]$ to a category $j \in [m]$ comes with a cost $c_{ij}$. Multiple objects can be mapped to the ...
WaterFox's user avatar
  • 139
0 votes
0 answers
51 views

Pushing Boxes, help me solve this graph problem!

Given a directed, acyclic graph with nodes representing boxes/objects at rest and edges that point to neighbouring boxes/objects in direct contact. Each node will be assigned a number that represents ...
Peter Mino's user avatar
1 vote
1 answer
90 views

Characterization of circular flow

We are given a directed graph $G$, capacity $u$, source $s$ and sink $t$. We call a flow from $s$ to $t$ a circular flow if the size of the flow is $0$. We say that function $l: E(G) \to R^{+}_{0}$ is ...
Hinko Pih Pih's user avatar
1 vote
1 answer
300 views

Maximum flow of a graph and minimum capacity of a s-t cut

Question: Find the maximum flow and minimum capacity of a s-t cut of the following graph. The capacity on every edge is 1 . The continuous edges have a flow of 0 and the dotted straight edges have a ...
Willem's user avatar
  • 177
2 votes
1 answer
57 views

Find cycles with fixed number of edges without shared vertices in a directed graph

I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ...
Kelvin's user avatar
  • 23
2 votes
1 answer
540 views

Linear Algebra Network Flow Problem. What happens if we allow the street to be a 2 way road.

For this problem, the direction of traffic flow is only in one way. Thus, they say that the constraints for x1,x2,x3,x4 must be greater or equal than 0. I don't understand why having a one way road ...
user20194358's user avatar
1 vote
1 answer
246 views

Initialization of the Network Simplex Method

I am studying Chapter 7 (Network Flow Problems) of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. On page 286 the authors briefly describe a way to deal with the ...
Kittayo's user avatar
  • 699
0 votes
0 answers
196 views

Uniqueness of minimum cost flow and reduced cost optimality condition

Let $G = (V, E)$ be a directed graph with edge costs $c: E \rightarrow \mathbb{Z}_{\geq 0}$ and edge capacities $w: E \rightarrow \mathbb{Z}_{\geq 0}$. Let $f^*: E \rightarrow \mathbb{R}_{\geq 0}$ be ...
endeavor's user avatar
  • 311

1
2 3 4 5
9