Stack Overflow
Stack Overflow

Questions tagged [max-flow]

The maximum-flow problem, a problem in computer science over a flow network

The maximum flow (max-flow) problem is a problem in computer science, studied in the theory of s, involving finding the maximum flow over a given flow network. It is closely related to the problem for graphs.

214 questions
63
votes
7 answers

How can I find the minimum cut on a graph using a maximum flow algorithm?

I need to find the minimum cut on a graph. I've been reading about flow networks, but all I can find are maximum flow algorithms such as Ford-Fulkerson, push-relabel, etc. Given the max flow-min cut theorem, is it possible to use one of those…
cesarbs
  • 894
  • 1
  • 8
  • 9
25
votes
5 answers

Fast max-flow min-cut library for Python

Is there a reliable and well-documented Python library with a fast implementation of an algorithm that finds maximum flows and minimum cuts in directed graphs? pygraph.algorithms.minmax.maximum_flow from python-graph solves the problem but it is…
Jukka Suomela
  • 12,070
  • 6
  • 40
  • 46
13
votes
1 answer

maximum bipartite matching (ford-fulkerson)

I was reading http://www.geeksforgeeks.org/maximum-bipartite-matching/ and http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm and am having trouble understanding. It seems the example is under the assumptions that each job can only accept…
senjougahara
  • 287
  • 1
  • 4
  • 13
10
votes
3 answers

Maximum Flow in Dynamic graphs

I'm looking for fast algorithm to compute maximum flow in dynamic graphs (adding/deleting node with related edges to graph). i.e we have maximum flow in G now new node added/deleted with related edges, I don't like to recalculate maximum flow for…
Saeed Amiri
  • 22,252
  • 5
  • 45
  • 83
10
votes
1 answer

image segmentation using graph cut with seed points

I'm working in medical image segmentation and I want to combine fuzzy connectedness algorithm with the graph cut, the idea is to segment the image with fuzzy connectedness the background and the foreground will be used as sink and source for the…
Born New
  • 103
  • 6
9
votes
0 answers

Implementing graph cut on image using Energy function

I was trying to extract the hair from a given image as described in the research paper, using the concept of energy minimisation, The energy function is dependent on both Prior probability and YCrCb colour likelihood histogram. The energy function…
ZdaR
  • 22,343
  • 7
  • 66
  • 87
8
votes
1 answer

What algorithm opencv GCGRAPH (max flow) is based on?

opencv has an implementation of max-flow algorithm (class GCGRAPH in file gcgraph.hpp). It's available here. Does anyone know which particular max-flow algorithm is implemented by this class?
Shai
  • 111,146
  • 38
  • 238
  • 371
8
votes
2 answers

All pair Maximum Flow

Given a directed weighted graph, how to find the Maximum Flow ( or Minimum Edge Cut ) between all pairs of vertices. The naive approach is simply to call a Max Flow algorithm like Dinic's, whose complexity is O((V^2)*E), for each pair. Hence for all…
sabari
  • 779
  • 2
  • 8
  • 14
7
votes
1 answer

Increase flow by changing only one edge after Ford-Fulkerson

Suppose that I've run the Ford-Fulkerson algorithm on a graph G = (V,E) and the result is a max-flow fmax, which is associated to a min-cut Xmin. I'm interested in increasing the flow as much as possible by increasing the capacity of any one edge…
Richard Gasol
  • 71
  • 1
  • 3
6
votes
1 answer

How to find if there is a simple path from vertex x to vertex y that includes the edge e

so I faced this question and I hope that someone can help me in it. Given an undirected graph G = (V, E), 2 vertices x,y and an edge e = (v,u). Suggest an algorithm to find if there's a simple path from x to y that includes the edge e. So the focus…
Mohamad S.
  • 199
  • 1
  • 9
6
votes
1 answer

Finding a Circulation in a Network with lower bounds

I can't understand how to find circulation flow in the network with lower bounds(not demands). I found next documents with problem description and solving…
KolKir
  • 859
  • 1
  • 8
  • 16
6
votes
1 answer

Min-cost-max-flow with boost::successive_shortest_path_nonnegative_weights

I need to calculate the min-cost-max-flow for a flow network using the boost::successive_shortest_path_nonnegative_weights() function available in the BGL (v 1_60_0). As specified in the documentation, the directed graph G=(V,E) that represents…
Filippo
  • 361
  • 1
  • 5
  • 16
6
votes
2 answers

Which min-cut does the Ford-Fulkerson algorithm find?

There can be multiple min-cuts in a network. E.g: has four min-cuts and Ford-Fulkerson finds the one "nearer" to s (the source). Can we say the same for all networks? That is, Ford-Fulkerson finds the cut nearest to the source? If true, how do we…
Apratim Bhattacharyya
  • 91
  • 3
6
votes
1 answer

How can I get the antichain elements in SPOJ-DIVREL?

Problem: http://www.spoj.com/problems/DIVREL In question, we just need to find the maximum number of elements which are not multiples (a divisible by b form) from a set of elements given. If we just make an edge from an element to its multiple and…
user3674243
  • 61
  • 4
6
votes
1 answer

Modification to Maximum Flow Algorithm

I've tried to solve a question about the maximum-flow problem. I have one source and two sinks. I need to find a maximum flow in this network. This part is general max-flow. However, both targets have to get same amount of flow in this special…
TheGost
  • 147
  • 1
  • 3
  • 8
1
2 3
…
14 15