Stack Overflow
Stack Overflow

Questions tagged [minimum-cut]

A problem in computer science related to graph theory

The minimum cut (min-cut) problem is a etic problem in computer science, studied in the theory of s. It is closely related to the problem for flow networks.

The problem is: given a weighted graph, find the cut that crosses edges with the smallest possible total weight.

30 questions
5
votes
1 answer

Max-Flow - Detect If A Given Edge Is Found In Some Min Cut

Given a network G=(V,E) , a max flow f and an edge e in E , I need to find an efficeint algorithm in order to detect whether there is some min cut which contains e. Another question is if I found out the e is contained in some min-cut, is it…
user975343
5
votes
1 answer

Finding the minimum cut in graph with Kruskal's algorithm?

We have already seen that spanning trees and cuts are intimately related. Here is another connection. Let’s remove the last edge that Kruskal’s algorithm adds to the spanning tree; this breaks the tree into two components, thus defining a cut (S,S)…
fdh
  • 5,256
  • 13
  • 58
  • 101
4
votes
1 answer

Randomized Min-Cut, Karger's Algorithm

I am implementing Karger's algorithm. From what I understand, the number of edges between the final two nodes is not always the Min Cut. What I am having trouble understanding is how do I actually get the min cut from this algorithm. I keep…
Flyingcows00
  • 223
  • 1
  • 11
3
votes
3 answers

Algorithm for splitting a connected graph into two components

Suppose I am given a weighted, connected graph. I'd like to find a list of edges that can be removed from the graph leaving it split into two components and so that the sum of the weights of the removed edges is small. Ideally I'd like to have the…
David Norman
  • 19,396
  • 12
  • 64
  • 54
3
votes
1 answer

Finding the lowest amount of edges in all minimum cuts in flow network

Given a network N, I want to find the minimum cut that has the lowest number of edges in it. I thought about: Find the maximum flow (with Dinitz algorithm for example) Increase the capacity function such that for every edge e c'(e)=c(e)+1, then use…
Yinon Eliraz
  • 317
  • 1
  • 6
  • 22
3
votes
1 answer

Find all edges in min-cut

Let (G,s,t,{c}) be a flow network, and let F be the set of all edges e for which there exists at least one minimum cut (A,B) such that e goes from A to B. Give a polynomial time algorithm that finds all edges in F. NOTE: So far I know I need to run…
miszu
  • 77
  • 1
  • 2
  • 5
2
votes
1 answer

How to get all the possible set of edges of graph that disconnects the graph ( satisfying minimum cut )

Imagine I have the graph below. Minimum cut of this graph is 2 which means it takes at least removing 2 edges to make this graph disconnected. I want to get all the possible set of edges that satisfy this number and removing them makes graph…
Mehdi Hamzezadeh
  • 366
  • 1
  • 8
2
votes
1 answer

s-t cut for undirected weighted graph

I recently got interested in graph theory. I came across the s-t cut for a directed graph. I learned online that the min-cut is equal to the max flow and there are standard algorithms out there that can solve the s-t min cut for a directed graph.…
Oliver Chang
  • 43
  • 5
2
votes
1 answer

Divide a graph into same size disjoint sets with minimum cut

Is there any algorithm or code that divide graph nodes into two or more disjoint sets that satisfy following conditions: first, only edges allowed to remove. second, edges are weighted and those that would be removed must has minimum weight(minimum…
m b
  • 61
  • 6
2
votes
1 answer

minimum cut between two arbitrary vertices given as input for an undirected unweighted graph

I have an undirected weighted graph and I need to find the minimum cut that separates two sets of vertices. I can modify my setup so as to reduce the problem to finding the minimum cut that separates two given vertices. I want to add that the…
user2844647
  • 163
  • 4
2
votes
0 answers

Minimal cuts vs Edge connectivity

Here is a question asking the connection between the edge connectivity of a graph and its minimal cuts. As we know, the edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For…
Galaxy
  • 853
  • 2
  • 11
  • 28
2
votes
2 answers

Find the minimum set of vertices in a DAG that disconnects a certain fraction of paths

The problem is given as follows: Given a DAG and a number 0 < p ≤ 1, return the minimum-cardinality set of vertices that disconnects at least a p-fraction of paths from a source (i.e., no incoming arcs) to a sink (i.e., no outgoing arcs). For p = 1,…
Dant3
  • 41
  • 4
1
vote
1 answer

I am trying to solve Min Cost problem in AMPL, but my objective function is 0

I am new to AMPL and doing MC problem. I have included my code. I asked earlier to help with other errors, at this moment program is working, but optimal solution is 0 and giving a strange error. What can be a problem? Maybe my constraints are…
AlenaCh
  • 21
  • 2
1
vote
0 answers

Finding the minimum cost set of nodes so that once removed, the graph is disconnected

It would be great if someone could help me. I have an undirected graph where every vertex has a weight and where no edges have weights. I want to find a set of nodes with minimum total weight for which their removal makes the graph disconnected. …
SaRa
  • 51
  • 5
1
vote
2 answers

Finding minimal cut of a flow network

I am trying to find a minimum cut of the following network I am using the following algorithm: Run Ford-Fulkerson algorithm and consider the final residual graph. Find the set of vertices that are reachable from source in the residual graph. All…
Simon
  • 2,643
  • 3
  • 40
  • 61
1
2