The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
154 views

Complexity of a parametrized min-cost flow problem

Consider the following min-cost flow variant: Input: a positively-weighted complete bipartite graph $G = (S, T, c)$ and extra vertices $s, t$ edges from $s$ to $S$ and from $T$ to $t$. lower ...
1
vote
0answers
181 views

Dinic Algorithm with limited vertices

Is it possible to construct a graph with 5 to 10 vertices for which the Dinic-Algorithm finds exactly |V|-1 blocking flows, and if so what does it look like?
3
votes
1answer
114 views

Network Flow with Non-contiguous Capacities

I have a problem that I can model as a minimum cost network flow. The only problem is that I need to be able to set the flow through some arcs to be either 0 or at least 5. That is, the arc cannot ...
2
votes
1answer
218 views

Minimum-Cost Flow Problem with Constraint on the Total Incoming/Outgoing Flow for the Vertices

Consider the standard minimum-cost flow problem presented here. I would like to add an additional set of constraints on the total incoming/outgoing flow for each vertex (excluding the source $s$ and ...
5
votes
2answers
2k views

Fastest way to find an s-t min-cut from an s-t max-flow?

Ford-Fulkerson can find sparse s-t flows in time linear in the size of the flow and number of nodes if the edges have unit capacity. How could I use a sparse s-t flow to find an s-t min-cut in time ...
1
vote
1answer
117 views

Max flow with conditional edges

Is anyone aware of a max flow algorithm where the edges are conditioned upon one another? Meaning if I send f units of flow from vertex a --> b, then I have to send .5*f* unit from a --> c.
7
votes
1answer
436 views

Goldberg&Tarjan: How to find a blocking flow in a graph

I want to implement the Goldberg & Rao algorithm for finding a maxflow in a graph. My problem is the update step where every paper and report is stating "In the resulting graph, find a blocking ...
3
votes
1answer
297 views

Can I get all min-cuts after executing Push-Relabel?

The push-relabel algorithm (here is push-relabel as pseudo-code) assigns a distance-label to each node. After executing push relabel, you have those distance labels and a max flow in a given network ...
23
votes
2answers
953 views

Are any of the state of the art Maximum Flow algorithms practical?

For the maximum flow problem, there seem to be a number of very sophisticated algorithms, with at least one developed as recently as last year. Orlin's Max flows in O(mn) time or better gives an ...
-1
votes
1answer
204 views

The existing bound on Edmonds-Karp doesn't seem to be tight

I'm reading CLRS's (Cormen et.a al) Introduction to Algorithm, and arrived at the maximum flow section. It shows that Edmonds-Karp algorithm runs in $O(E^2V)$ time by showing that: 1) If we let ...
6
votes
1answer
186 views

multi-commodity flow acyclic digraphs

I am faced with the following question on max. integer multiflow: INSTANCE: An acyclic directed graph G=(V,E), a capacity function c:E→N, k pairs of vertices (si,ti) and a demand function ...
2
votes
2answers
328 views

Viapath as a maximum flow problem

Let $G = (V, E)$ be a graph and $a$, $b$, $x$ $\in V \ $ different vertices. I have seen stated that the problem of finding a simple path from $a$ to $b$ passing through $x$ can be formulated as a ...
5
votes
1answer
836 views

Minimum path edge-cover or minimum flow with unit capacities and DAGs

I have a directed acyclic graph (DAG) such that there can only be at most one edge between any two nodes (ie, only one (i,j) can exist between i and j). I need to find the the smallest set of paths ...
0
votes
2answers
1k views

shortest path & max flow

I am trying to improve my algorithmic knowledge during the summer break and i found this problem in a book. We have an undirected graph $G=(V,E$) with starting node $s\in V$ and last node $t \in V$ ...
4
votes
0answers
186 views

Integral k-multicommodity flow with demands on acyclic digraphs wirh maximum outdegree two

It is well-known that different variants of Multicommodity flow problem are NP-complete. What is the complexity of the following variant, that is, the integral k-multicommodity flow problem with ...
21
votes
1answer
1k views

Maximum flow using Ford-Fulkerson and DFS

This question is about the time complexity of the Ford-Fulkerson maximum flow algorithm when using DFS to find augmenting paths. There is a well-known example showing that using DFS one can need a ...