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.

Filter by
Sorted by
Tagged with
0
votes
0answers
20 views

Max flow problem of a connected graph

For any directed graph Is the maximum flow is always unique ?
1
vote
1answer
18 views

Covering maximal number of sets using fixed number of elements

I've encountered some problem which seems general enough to have already been solved. There is a set of objects $O=\{o_1, o_2,\dots,o_k\}$ and a family of sets $A_1,A_2,\dots,A_t \subseteq O$. For ...
1
vote
0answers
18 views

Maximum edge-disjoint flow

Consider the case where you have two types of flow, let's say "red" flow and "blue" flow. You want to send $k_r$ red flow and $k_b$ blue flow through a DAG $G$ from a source $s$ to a sink $t$ in such ...
0
votes
0answers
22 views

Optimize Max-flood algorithms bounds

In distributed algorithms, The Max Flood algorithms finds the leader in a network of processes In O(diam) time and with |E|*diam ...
1
vote
2answers
48 views

Find max flow in a network with all capcities of $\sqrt 2$ and one with 2

Given a graph $G(V, E)$ with capacities on the edges such that all edges have a capacity of $\sqrt2$ apart from one edge with a capacity of 2. need to find max flow efficiently. I can run Dinic on ...
4
votes
1answer
78 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}$ ...
0
votes
1answer
53 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-...
2
votes
0answers
22 views

FPTAS algorithm to find flow at each link for multi commodity flow problem?

Given a graph $G$ and $K$ commodities to route from source to destination. I want to find, what is the maximum beneficial flow for each of the commodities and the relevant paths. I understand the ...
2
votes
1answer
40 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. ...
2
votes
1answer
32 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 ...
0
votes
0answers
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 ...
3
votes
1answer
230 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 ...
0
votes
0answers
23 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 ...
0
votes
0answers
32 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). ...
1
vote
0answers
25 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 ...
0
votes
1answer
47 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 ...
3
votes
2answers
130 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 ...
1
vote
0answers
42 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 ...
0
votes
1answer
239 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 ...
0
votes
0answers
21 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 ...
2
votes
1answer
46 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 ...
0
votes
1answer
25 views

default TCP Maximum Segment Size

Why default TCP Maximum Segment Size is 536? If found this line in TCP/IP by behrouz forouzan
3
votes
1answer
398 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 ...
1
vote
1answer
39 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 ...
0
votes
1answer
27 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 ...
2
votes
1answer
40 views

Network flow - minimum flow through edge

In my max flow network, I would like to have an edge with upper bound of the flow (a.k.a. edge capacity) $c_{max}$. However, I would also like to add a lower bound for the flow through the edge, $c_{...
0
votes
0answers
17 views

How to divide services and capacities in a graph?

Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...
3
votes
1answer
103 views

Relative vertex capacity in max flow algorithm

I am designing a network for a max flow and would appreciate the following feature: Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let ...
1
vote
1answer
74 views

How to solve the minimum-cost flow problem on a complete graph, with a concave cost function of flow for each edge?

Here is the problem: Input: A series of source/sink nodes at fixed positions with given outwards/inwards flow Edges are NOT specified. The edges can connect any nodes. The total source and sink ...
2
votes
0answers
27 views

Transit scheduling using flow networks

I am studying the maximum/minimum flow question, and was given the following problem: A traveling agency has $n$ destinations on their service map, and it intends to maintain them with minimum ...
3
votes
1answer
71 views

is it possible to find the maximal min cut in polynomial time?

A maximal minimum cut is a minimum capacity cut with the largest number of edges.
1
vote
1answer
37 views

Will a node with no incoming arc or no out coming arc affect the maximum flow?

So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?
0
votes
0answers
78 views

Minimum-cut with Maximal number of edges

My question is: in a DAG, each edge has a different value of capacity, we can assume these capacities are integers multiples of the total number of edges. Also, sometimes we can have many minimum cuts,...
4
votes
1answer
1k views

Minimum-cut with minimum number of edges

I am sure many folks here know the famous min-cut max-flow theorem - the capacity of the minimum cut is equal to the maximum flow from a given source, s, to a given sink, t, in a graph. Firstly, let'...
0
votes
1answer
37 views

Efficient algorithm for assigning weights to nodes in graph to create steady state flow

I'm looking for an efficient algorithm (at least polynomial in the size of the graph, preferably linear) for the following problem: Definitions: Given a graph $(V,E)$, with non-negative weights ...
0
votes
1answer
70 views

Maximum flow with maximum flow on specific edge

I am trying to solve the following problem: We're given a network flow $(V,E,c,s,t)$ and an edge $(u,v)$. We have to provide an algorithm that computes the maximum flow which has maximum flow on $(u,...
0
votes
0answers
8 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: ...
1
vote
1answer
37 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 ...
1
vote
1answer
60 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 ...
3
votes
1answer
165 views

Min cut of at most k edges

I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle. Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow ...
0
votes
0answers
34 views

Check valid flow in a graph

For a flow network $G=(V,E)$ where $s,t \in V$ and capacities $c_e>0$ for $e \in E$. A flow $f$ is given. How can I check whether of not $f$ is a valid flow within the network?
0
votes
0answers
29 views

Max flow through a specific edge

What i'v tried doing so far is to find a simple path from s to t containing e as well as some "bottle-neck edge" of maximal value (i.e. a simple path from s to t, containing e, whose minimum ...
0
votes
0answers
32 views

Which computational framework lies behind the Chinese “Social Credit System”?

BACKGROUND The Social Credit System is a data-driven reputation system which draws on several sources to label various entities, namely businesses and individual citizens, with a trustworthiness ...
0
votes
0answers
43 views

Proof of lemma from Hong's article about multi-threaded max flow algorithm

I'm struggling to prove Lemma 3 and Lemma 4 from an article about parallel version of push-relabel algorithm: A lock-free multi-threaded algorithm for the maximum flow problem. Lemma 3. Any trace ...
3
votes
1answer
98 views

Forcing an edge to be in S-T min-cut

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e. So, I tried couple of steps, first, ...
2
votes
1answer
41 views

Maximum Flow in a Network

Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$. Prove or disprove: The value of a maximum flow for $N$ can’t be $56$. I'm trying to figure out how to ...
2
votes
1answer
31 views

Current value of flow in a network

Confused about a question regarding flow networks. Question is: Given the network below, what is the current value of flow in this network? Does the current flow of a network refer to the maximum ...
0
votes
0answers
53 views

What is the most efficient way to solve a workshop scheduling problem?

I am trying to design an algorithm to solve a workshop scheduling problem. The problem is as follows: I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
1
vote
0answers
33 views

Binary flow in max flow problem

is there a way ensure that there only is flow through vertices c and d and not e or through d and e and not c. But not both at the same time. With an simple extension it is possible to put also ...
4
votes
2answers
121 views

Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...

1
2 3 4 5 6