The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
15 views

Upper Bound Difference between Min Cut and Max cut?

Quick question: Are there any known upper bounds for the difference between the value of a maximum cut(:=M) and a minimum cut(:=m) in a flow network? (|M - m| <= f for some function f)
5
votes
1answer
105 views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
-1
votes
1answer
110 views

Prove that Ford-Fulkerson can decide if there is more than one min cuts

Probelm: Deciding whether a network flow graph has more than one min cut. Optimal running time: O(V^2*E). I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and ...
2
votes
4answers
372 views

Why is this flow a max flow?

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how ...
0
votes
0answers
18 views

Minimum Augmenting pahts in Ford Fulkerson Algorithm

Based on the Ford Fulkerson method the choice of the next path to Augment is crucial so the algorithm can halt quickly. Is there any bound on the minimum number of paths that need to be "augmented" ...
3
votes
1answer
173 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
2
votes
1answer
23 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of ...
3
votes
1answer
62 views

Maximum Flow with Binary Capacities

Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow ...
-1
votes
1answer
32 views

Max-Flow Min-Cut Theorem Intuition

What is the intuition behind the Max-Flow Min-Cut Theorem? I know that the Min-Cut is the dual of Max-Flow when formulated as a linear program, but the result seems artificial to me.
1
vote
0answers
41 views

Network clearance algorithms

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., ...
0
votes
3answers
68 views

Literature on network-flow (optimization) approximation algorithms

I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree. However, I have been looking in several well-known ...
3
votes
1answer
134 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} ...
2
votes
1answer
93 views

“Minimum” maximum flow with extra capacities

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
0
votes
0answers
19 views

Algorithm: “Minimum” maximum flow with extra capacities [duplicate]

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
1
vote
0answers
64 views

Does Edmonds Karp take back-edges into account?

I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm. This is a problem with flow networks. As I understand the algorithm, it consists on taking ...
2
votes
1answer
42 views

Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues. I have ...
3
votes
1answer
62 views

Unsplittable flow in capacitated networks

I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
1
vote
0answers
17 views

MaxSNP flow problems

Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
1
vote
0answers
94 views

Getting ALL negative weight cycles of a graph using Bellman-Ford

I'm doing a min cost assignation problem to assign doctors to their working days for a hospital. After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle ...
-1
votes
1answer
45 views

How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph. Could someone explain how ...
7
votes
0answers
137 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
1
vote
1answer
86 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
0
votes
0answers
22 views

Maximum Flow - Proof of Total flow is equal to flow from source is equal to flow to the sink

In Maximum Flow of CLRS Book Chapter-26,in the section Lemma 26.1, the proof of total flow in the network is given as below. $|f| = f(s,V) $ [by definition] $= f(V,V) - f(V-s,V)$ [by Lemma 26.1 part ...
2
votes
1answer
30 views

Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
1
vote
1answer
60 views

Ford-Fulkerson algorithm clarification

In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results): I ...
2
votes
0answers
22 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
-1
votes
1answer
34 views

Determine whether there is a valid rounding in a table of numbers

I was told this question would be better suited here: Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 ...
0
votes
0answers
41 views

sum of max flow in residual graph and value of flow

My teacher today explained us this . Consider a network and suppose that at any stage during the application of the Edmonds Karp algorithm to find the max flow, let ...
3
votes
1answer
111 views

Finding a subset in bipartite graph violating Hall's condition

We are given a bipartite graph of $n \leq 200$ vertices in both the first and the second partite set. Let $U$ be some set of vertices in the first set, and $V$ those vertices from the second that are ...
3
votes
0answers
69 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
2
votes
0answers
47 views

Max Flow on low depth DAGs

I have a family of acyclic networks in which every path from the source of a given network to its target has length exactly $3$. I'm aware of a publication that in general, finding a max flow in a DAG ...
4
votes
1answer
138 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
0
votes
1answer
74 views

For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges? [closed]

Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?
1
vote
3answers
142 views

Can not follow the example for max-flow-min-cut on Wikipedia

This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut ...
2
votes
2answers
163 views

Don't understand this graph definition

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
2
votes
1answer
62 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut ...
2
votes
2answers
195 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
1
vote
1answer
51 views

Minimum cut versus sparsest cut? [closed]

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
1
vote
1answer
148 views

maximum bipartite matching

I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that finds a maximum-sized subset of the rooks such ...
0
votes
0answers
47 views

Picking an optimal initial congestion window size (high bw, high latency and short bursts)?

What is a known strategy to approach a situation where short bursts of data are being sent very often over a high bandwidth, high latency cable? I am aware of cubic but even that does not utilize a ...
5
votes
3answers
259 views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
0
votes
1answer
52 views

Network Flow with multiple connected subsets

Given a set of buyers, houses, agents with the following constraints: Agents only know a subset of buyers Agents only know a subset of houses Agents can only do some amount of transactions ...
6
votes
1answer
82 views

Why can't you write the 2-paths problem as a max-flow problem?

This is a follow-up question to this. Consider the 2-paths problem: Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and ...
2
votes
0answers
331 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
90 views

Prove that every maximal flow yields the same minimal cut

Hi I'm trying to prove the following proposition: Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where ...
1
vote
0answers
46 views

residual network for a network with lower and upper bounds?

How does one construct the residual network in such a case? The formula is for edge $(u, v)$ is $$rf(u,v) = (c_{\mathrm{upper}}(u,v) - f(u,v)) + (f(v,u) - c_{\mathrm{lower}}(v, u))\,,$$ where ...
5
votes
0answers
226 views

Understanding Dinic's algorithm using dynamic trees

I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan ...
1
vote
1answer
114 views

Finding paths from the result of max flow [closed]

Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them. I would like to enumerate all possible sets of paths that comprise the maxflow. That ...
2
votes
2answers
129 views

State machine with knowledge of prior states?

I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well. Below is an example graph ...
2
votes
1answer
78 views

Multicommodity circulation formulation

On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...