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
0answers
45 views

How to formulate a condition for a flow graph to have valid output/input over any possible set of activations/deactivations of sources/sinks

I have a Graph G with some set of sources and sinks. Each edge, source and sink has a maximum capacity of 1. A node divides its inputs evenly among the output edges. (Might not be relevant to the ...
2
votes
1answer
57 views

Write down linear system describing the flow in the network

Network question I currently have the following answer: X1 - X2 - X3 - X4 = 0 X2 = 1 X3 = -1 X4 = 5 But the answer sheet says this is correct: ...
1
vote
0answers
149 views

Dual problem to max flow with leaking and minimal flow

So I have a graph $G=(V,E)$ with max capacity and minimal flow on the edges (denoted $C_{i,j}, l_{i,j}$ respectively). In addition to that I have a leaking component $r_v$ for all $v\in V\backslash \{...
1
vote
0answers
99 views

Optimizing flow within graph, for gossip protocol optimization

What are some approaches to optimize a directed graph (v,e), where the vertices are nodes participating in the transmission of a message to a subset of the vertices using the gossip protocol, and ...
1
vote
0answers
141 views

Maximum flow and cyclic partitions

The digraph $ G = (V, E)$ is called cyclic if $\exists k ≥ 1$ circuits in $ G, C_1, . . . , C_k,$ whose set of vertices, $V (C_1), . . . , V (C_k),$ forms a partition of $V (G)$. Prove that you can ...
2
votes
2answers
376 views

Application of Min Cost Flow to hostel bookings

A hostel made a mistake concerning their bookings for 2017 and took many reservations without checking for free rooms in these periods. Every reservations is made for exactly one room and one period ...
1
vote
0answers
124 views

Network of flows

Let $G=(V,E)$ be a digraph. We call it "cyclable" if there exists $k$ $\geq$ 1 circuits in $G$,$C_1$,...$C_k$, of which sets of vertices, V($C_1$),...,V($C_k$) , makes a partition of $V(G)$. I must ...
1
vote
0answers
76 views

Is it possible to have a weighted graph (integer weights are also ok) where the max flow can be obtained in a non unique way?

My question is simple: given a DAG $G=(V,E,C)$ where $V$ is the set of nodes, $E \in V \times V$ is the set of edges,$C$ is a weight function that associate to each link a number that represent the ...
1
vote
1answer
1k views

Find the maximum number of edge-disjoint paths

Supposing I have an undirected graph G = (V, E); which polynomial-time algorithm can I use, for two vertices s and ...
4
votes
2answers
569 views

Is there an effective algorithm to solve this binary integer linear programming?

I am an applied math undergraduate student. On my project, I come across an integer linear programming question as follow: Given $x_0,x_1,...,x_n$: $\forall$ i $\in$ [0,n], $x_i$ = 0 or 1 min Z = $\...
5
votes
1answer
5k views

Definition of capacity of cut in a flow network

In the flow network below, an S-T cut is made. The net flow across the cut is $12-4+11=19$. The capacity of the cut is $12+14=26$. The "backwards" edge $(v_3,v_2)$ is not counted when calculating ...
3
votes
1answer
918 views

Find the minimum amount of edges in a graph to improve flow

Given a flow network with maximum flow $f$, I want to find the minimum amount of edges, that if their capacity will increase, the maximum flow will increase. I have tried using BFS to find the amount ...
0
votes
1answer
787 views

A game: When can you merge two directed graphs?

I am trying to consider the conditions under which you can win the following directed graph game: Graph merging game. Fix an acyclic directed graph $G$; its vertex set is $V$, and its edge set is $E$....
0
votes
0answers
272 views

Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
31
votes
4answers
22k views

Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
0
votes
0answers
169 views

Finding a minimum cut for an (s-t) flow: why not just cut the start/end edges?

Most examples I've seen involve cuts snaking through graphs picking off various edges. My question is why not simply do a cut either involved the edges leaving the source or the edges entering the ...
0
votes
1answer
131 views

Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
2
votes
0answers
642 views

Maximum flow on a directed, acyclic graph

What would be the best algorithm to use for finding max-flow/min-cut on a directed, acyclic graph with integer flows, capacities, and vertex demands? I've been thinking Dinic's Algorithm would be ...
2
votes
0answers
242 views

Weighted Katz Centrality

Given a graph G with n nodes and adjacency matrix A, the Katz Centrality measure, K(G), is given by $K(G)[i] = \sum_{k=1}^{\infty}\sum_{j=1}^{n}\alpha^k(A^k)_{ji}$ s.t. $\alpha$ is an attenuating ...
0
votes
1answer
1k views

Network flows - formulating the max flow problem as a min cost flow problem

I have been trying to look this up, and I could only find a min cost flow to max flow transformation on the internet. Apparently, this transformation can be done by setting the costs to 0. Another ...
1
vote
1answer
35 views

What are those weighed graphs called?

Let $G = (V, E)$ be a directed graph, and define the weight function $f : V \sqcup E \to \mathbb{R}^+$ as follows: sum of weights of vertices is 1, if a vertex has edges coming out of it, their ...
1
vote
1answer
339 views

Max-flow/min-cut to determine densest subgraph

I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: https://hal.archives-ouvertes.fr/inria-...
2
votes
0answers
46 views

Why it is not trivial that $Z_k$-flow gives $k$-flow

In Diestel graph theory book, theorem 6.3.3 (Tutte 1950) states: A multigraph admits a $k$-flow iff it admits a $\mathbb{Z}_k$-flow. I don't understand why do we need a proof, because, by definition,...
1
vote
1answer
392 views

Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
1
vote
1answer
50 views

It would be nice if someone has some idea! (A Diophantine system associated with a network flow)

Assume that we are given a connected network flow with n nodes, $\{1, ..., n\}$, and m arcs. For each arc, say $x_{ij}$ from node i to node j, there is a maximum capacity level given as $M_{ij}$. ...
0
votes
2answers
2k views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
2
votes
0answers
202 views

What measures of centrality exist for fully connected networks with weighted directed edges?

I have a network of cities with transport links between them. The transport links are not symmetric in both directions, therefore asymmetric edges between nodes. There is a variable number quantifying ...
4
votes
3answers
3k views

Group Theory vs Graph Theory [closed]

I would like to know that, For a given graph can we find an associated finite group? If there are more than one such group, what are the differences and similarities between them? Here by a graph I ...
3
votes
1answer
77 views

Is it possible to turn a weighted adjacency matrix into an ODE compartment model?

I have an idea for a project that hinges on this idea. Lets say we have an adjacency matrix of a DiGraph where the i,j entry represents an out-going edge from node i to node j and at this position ...
1
vote
1answer
456 views

Max/Min flow of a network

I have a network: How do I figure out the maximum and minimum possible flow through each undefined branch?
1
vote
1answer
2k views

Airline scheduling using minimum network flow

Consider the following table for an airline company:                          &...
1
vote
0answers
512 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 ...
2
votes
1answer
1k 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 ...
1
vote
0answers
83 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
1answer
88 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
1k 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 V^{-}(...
1
vote
1answer
103 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,...). ...
1
vote
1answer
496 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
0answers
938 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
85 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
84 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 ...
1
vote
1answer
917 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?
4
votes
1answer
346 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
162 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 along ...
1
vote
2answers
133 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
26 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
175 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 ...
2
votes
2answers
1k 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
394 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
1answer
729 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 ...

1 2 3
4
5
7