A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [network-flow]

Network flows are used to model concepts like traffic or water pipe systems. The basic idea is to move as many units of flow from source to sink nodes via edges with limited capacity.

255 questions
Filter by
Sorted by
Tagged with
35 views

### Maximum flow on a tripartite graph

I have to solve an assignment problem between $\{1,\dots, N\}$ agents and $\{1,\dots, M\}$ objects, which comes to maximize : \begin{equation} \sum_{ij}\beta_{ij}x_{ij} \end{equation} where $x_{ij}$ ...
31 views

### Given a network flow find if there's a min cut that only one of the given edges lay on it

Given a network flow $G=(V,E)$ with capacity function $C$ source $s$ and hole $t$, and given 2 edges $e_1 , e_2$. Find if there exists a min-cut such that only one of the edges belongs to the min-...
12 views

### What is the FPTAS algorithm to find flow at each link for multi commodity flow problem?

I have a graph and K commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodity and the relevant paths. I understand the problem in ...
32 views

### Max flow algorithm for floating-point weights and E~=10*V

Could you, please, suggest a maximum flow algorithm for a graph with floating-point weights and the number of edges approximately equal to the number of vertices? I.e. ...
22 views

### Edmonds-Karp Algorithm with both directed and undirected edges?

How would this work and be implemented? If you have directed edges pointing away from the source to a bunch of other verticies, and directed edges pointing from those vertices to a sink, but have ...
29 views

### Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
162 views

### find the union of all min cuts of a flow network

I'm trying to solve the following question : Given a flow network $N = (G=(V,E),c,s,t)$. Let $\mathcal F$ be the set of all minimum cuts. Prove that $\mathcal F$ is closed under intersections and ...
16 views

### edmond karp proof

which contradicts our assumption that ıf $d_f'(s,v)<d_f(s,v)$. We conclude that our assumption that such a vertex exists is incorrect I can't comprehend the proof above for edmond karp algorithm ...
21 views

### Stop and Wait protocol in a half duplex scheme

glad i found this site. would appreciate help with this: in picture i uploaded there's a state diagram of a "stop and wait" protocol in a half duplex channel. we assume current status is (10A). ...
21 views

### Getting rid of negative-cost edges in min-cost max-flow algorithmically

I have a min-cost max-flow problem. The designed network (without cycles) gives correct results using cycle cancelling, but it is way too slow. I would like to get rid of negative edges so that I can ...
38 views

### Network Flow - Minimum flow in a network

I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges. In a course ...
45 views

### Smallest $s$-component in mincut

Suppose there is a directed graph $G=(V,E)$, with source $s$ and sink $t$, and I compute the max flow on it. Then I know that I can find a min-cut $(A,B)$, by letting $A$ be the set of vertices that ...
24 views

### Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
197 views

### Inviting an optimal subset of persons such that all friends of a person invited are invited

Let's say that you want to invite a person $u$ in party $P$. The person $u$ will join the party if and only if all the friends of $u$ will join the party as well. Otherwise, $u$ will reject your ...
20 views

### Creating capacity graph for a list of flights?

I have a list of flights and for each flight, I have information like source, destination, flight capacity, arrival time, departure time. There are only 8 distinct values that are populated in the ...
42 views

### Proving that max flows of undirected graph and equivalent directed graph are equal

There is an undirected graph $G$. A graph $H$ is constructed by changing each edge $(a,b)$ in $G$ to a pair of directed edges $(a,b)$ and $(b,a)$. How to prove that the maximum flow in $H$ is equal to ...
24 views

### default TCP Maximum Segment Size

Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan
179 views

### how to check whether a flow network contains unique maximum flow?

I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum ...
30 views

### Intuition behind min cut in a flow network? Whether it's baseball elimination or project selection

I was wondering if someone can give me a general definition of a min-cut besides it being the max flow of a network. For example, in the baseball elimination problem, if we wanted to find out if ...
17 views

### Relabel to front, what does topological sort according to admissible network mean?

In the CLRS book it says that "relabel to front" algorithm, which solves the maximum-flow problem, maintains a list of topologically sorted vertices in the admissible network and that vertices with ...
36 views

7 views

### What is the average time for a node to transmit on the shared medium for Ethernet? (IEEE 802.3)

Suppose a shared ethernet link L, in which for nodes T1-T4 and a router R are connected: ...
34 views

### Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
53 views

### Minimum cost max flow network problem with an alternative flow cost

Is there a standard name or a reference for the network flow problem that looks very similar to the minimum cost maximum flow problem, only the flow cost that I wish to minimize isn't sum of edge.flow ...
136 views

98 views

### Confused with the proof that Edmonds-Karp always monotically increases the shortest-paths

The proof for the lemma from "Introduction to Algorithms by Cormen et. al." is not clear for me. I can't comprehend a few things. Here is a lemma and its proof. My questions are below. The notation ...