The tag has no usage guidance.

learn more… | top users | synonyms

1
vote
0answers
22 views

Finding if a feasible flow exists in a minimum cost flow problem

I've been trying to understand the generic methodology for finding a flow with a certain value (satisfying all demand criteria) with a minimum corresponding cost. I know that this might sound somewhat ...
3
votes
1answer
22 views

Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

I stumbled across this question and answer (source): Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine ...
0
votes
0answers
9 views

Proving the Multiway cut problem is NP Complete [duplicate]

Problem Statement: Given k nodes: $$ u_1, u_2, u_3..., u_k $$ remove edges of total minimum weight that separates $u_i$ from $u_j$ for all $i != j$ for all k >= 3 I just need some help identifying ...
0
votes
1answer
30 views

How the website owner keep track of your times of access? [closed]

To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP ...
1
vote
0answers
13 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil ...
1
vote
0answers
35 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
1
vote
1answer
78 views

Does a path exist going through each color only once?

I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once. I think this problem can ...
0
votes
1answer
61 views

What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am ...
0
votes
0answers
39 views

Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement: the flow value can increased along an augmenting path $p$ in a residual network ...
-2
votes
1answer
74 views

Maximum flow, where such paths as source$\to$node$\to$sink must be ignored

How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths ...
1
vote
1answer
38 views

Why not use the channel capacity as the sliding window size?

In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%. What is the logic behind not doing this? ...
0
votes
1answer
48 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the ...
1
vote
0answers
70 views

Possible paths in pipe network, without loops and with some one-way valves

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 ...
1
vote
1answer
23 views

Flow in a network: Conservation of flow definition

This might be too easy... But I just don't get it. I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network ...
11
votes
1answer
241 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
207 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
398 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
32 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" ...
4
votes
1answer
256 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
42 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
80 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
59 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
44 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
86 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
205 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
117 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
99 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 ...
3
votes
1answer
105 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
89 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
20 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
138 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
60 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 ...
10
votes
0answers
251 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
114 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 ...
2
votes
1answer
36 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
100 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
23 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
36 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
57 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
127 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
86 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
55 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
157 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
85 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
184 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
169 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
77 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
252 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
84 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 ...