553:
20:
135:
In a weighted, undirected network, it is possible to calculate the cut that separates a particular pair of vertices from each other and has minimum possible weight. A system of cuts that solves this problem for every possible vertex pair can be collected into a structure known as the
128:, the minimum cut separates the source and sink vertices and minimizes the total sum of the capacities of the edges that are directed from the source side of the cut to the sink side of the cut. As shown in the
192:
problems are a family of combinatorial optimization problems in which a graph is to be partitioned into two or more parts with additional constraints such as balancing the sizes of the two sides of the cut.
23:
A graph and two of its cuts. The dotted line in red represents a cut with three crossing edges. The dashed line in green represents one of the minimum cuts of this graph, crossing only two edges.
345:
413:
237:
179:
369:
276:
506:
450:
194:
54:
Variations of the minimum cut problem consider weighted graphs, directed graphs, terminals, and partitioning the vertices into more than two sets.
478:
561:
132:, the weight of this cut equals the maximum amount of flow that can be sent from the source to the sink in the given network.
595:
590:
281:
40:
585:
57:
The weighted min-cut problem allowing both positive and negative weights can be trivially transformed into a weighted
213:
and edge weights are their distances. This is however often impractical due do the high computational complexity for
537:
243:
129:
454:
82:
74:
374:
250:
value. In this case, some algorithms used in maxflow problem could also be used to solve this question.
78:
81:
provides an efficient randomized method for finding the cut. In this case, the minimum cut equals the
348:
571:
incorrectly led you here, you may wish to change the link to point directly to the intended article.
198:
137:
529:
202:
104:, this problem can be solved in polynomial time, though the algorithm is not practical for large
48:
44:
473:
469:
521:
487:
429:
216:
206:
70:
505:
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M. (1994).
189:
73:, weighted graphs limited to non-negative weights can be solved in polynomial time by the
158:
354:
261:
51:
of the vertices of a graph into two disjoint subsets) that is minimal in some metric.
579:
151:, this problem can be solved in polynomial time. However, in general this problem is
89:
533:
210:
148:
125:
28:
424:
152:
100:
connected components by removing as few edges as possible. For a fixed value of
58:
564:
includes a list of related items that share the same name (or similar names).
525:
19:
552:
491:
116:
When two terminal nodes are given, they are typically referred to as the
247:
88:
A generalization of the minimum cut problem without terminals is the
432:, an analogous concept to minimum cuts for vertices instead of edges
209:
method, where the nodes are data samples assumed to be taken from a
143:
A generalization of the minimum cut problem with terminals is the
18:
347:
distinct minimum cuts. This bound is tight in the sense that a
96:, in which the goal is to partition the graph into at least
474:"A Polynomial Algorithm for the k-cut Problem for Fixed k"
568:
197:
can be viewed as a specific case of normalized min-cut
16:
Partition of a graph by removing fewest possible edges
377:
357:
284:
264:
219:
161:
77:. In the special case when the graph is unweighted,
340:{\displaystyle {\binom {n}{2}}={\frac {n(n-1)}{2}}}
407:
363:
339:
270:
231:
173:
301:
288:
558:Index of articles associated with the same name
246:, 2 nodes' Minimum cut value is equal to their
61:problem by flipping the sign in all weights.
8:
147:-terminal cut, or multi-terminal cut. In a
378:
376:
356:
310:
300:
287:
285:
283:
263:
218:
160:
195:Segmentation-based object categorization
442:
507:"The Complexity of Multiterminal Cuts"
7:
408:{\displaystyle {\frac {n(n-1)}{2}}}
205:. It can also be used as a generic
479:Mathematics of Operations Research
292:
14:
551:
396:
384:
328:
316:
278:vertices can at the most have
1:
69:The minimum cut problem in
612:
550:
526:10.1137/S0097539792225297
514:SIAM Journal on Computing
244:max-flow min-cut theorem
130:max-flow min-cut theorem
468:Goldschmidt, Olivier;
451:"4 Min-Cut Algorithms"
409:
365:
341:
272:
254:Number of minimum cuts
233:
232:{\displaystyle k>2}
175:
75:Stoer-Wagner algorithm
65:Without terminal nodes
24:
410:
371:vertices has exactly
366:
342:
273:
234:
176:
22:
596:Network flow problem
591:Graph theory objects
492:10.1287/moor.19.1.24
375:
355:
282:
262:
217:
159:
199:spectral clustering
174:{\displaystyle k=3}
112:With terminal nodes
586:Set index articles
470:Hochbaum, Dorit S.
405:
361:
337:
268:
229:
203:image segmentation
171:
79:Karger's algorithm
25:
562:set index article
403:
364:{\displaystyle n}
335:
299:
271:{\displaystyle n}
83:edge connectivity
603:
572:
555:
545:
544:
542:
536:. Archived from
511:
502:
496:
495:
465:
459:
458:
453:. Archived from
447:
430:Vertex separator
414:
412:
411:
406:
404:
399:
379:
370:
368:
367:
362:
346:
344:
343:
338:
336:
331:
311:
306:
305:
304:
291:
277:
275:
274:
269:
238:
236:
235:
230:
180:
178:
177:
172:
146:
107:
103:
99:
93:
611:
610:
606:
605:
604:
602:
601:
600:
576:
575:
574:
573:
566:
565:
559:
549:
548:
540:
509:
504:
503:
499:
467:
466:
462:
449:
448:
444:
439:
421:
380:
373:
372:
353:
352:
312:
286:
280:
279:
260:
259:
256:
215:
214:
190:Graph partition
187:
157:
156:
144:
114:
105:
101:
97:
91:
67:
17:
12:
11:
5:
609:
607:
599:
598:
593:
588:
578:
577:
557:
556:
547:
546:
543:on 2018-12-25.
520:(4): 864–894.
497:
460:
457:on 2016-08-05.
441:
440:
438:
435:
434:
433:
427:
420:
417:
415:minimum cuts.
402:
398:
395:
392:
389:
386:
383:
360:
349:(simple) cycle
334:
330:
327:
324:
321:
318:
315:
309:
303:
298:
295:
290:
267:
255:
252:
228:
225:
222:
186:
183:
170:
167:
164:
140:of the graph.
138:Gomory–Hu tree
113:
110:
85:of the graph.
66:
63:
15:
13:
10:
9:
6:
4:
3:
2:
608:
597:
594:
592:
589:
587:
584:
583:
581:
570:
569:internal link
563:
554:
539:
535:
531:
527:
523:
519:
515:
508:
501:
498:
493:
489:
485:
481:
480:
475:
471:
464:
461:
456:
452:
446:
443:
436:
431:
428:
426:
423:
422:
418:
416:
400:
393:
390:
387:
381:
358:
350:
332:
325:
322:
319:
313:
307:
296:
293:
265:
258:A graph with
253:
251:
249:
245:
240:
226:
223:
220:
212:
208:
204:
200:
196:
191:
184:
182:
168:
165:
162:
154:
150:
141:
139:
133:
131:
127:
123:
119:
111:
109:
95:
86:
84:
80:
76:
72:
64:
62:
60:
55:
52:
50:
46:
42:
38:
34:
30:
21:
538:the original
517:
513:
500:
483:
477:
463:
455:the original
445:
257:
241:
211:metric space
188:
185:Applications
149:planar graph
142:
134:
126:flow network
121:
117:
115:
87:
68:
56:
53:
36:
32:
29:graph theory
26:
425:Maximum cut
201:applied to
155:, even for
59:maximum cut
33:minimum cut
580:Categories
437:References
207:clustering
71:undirected
486:: 24–37.
391:−
323:−
49:partition
472:(1994).
419:See also
120:and the
90:minimum
534:1123876
248:maxflow
242:Due to
153:NP-hard
124:. In a
37:min-cut
567:If an
532:
118:source
560:This
541:(PDF)
530:S2CID
510:(PDF)
43:is a
41:graph
39:of a
224:>
122:sink
94:-cut
31:, a
522:doi
488:doi
351:on
108:.
47:(a
45:cut
35:or
27:In
582::
528:.
518:23
516:.
512:.
484:19
482:.
476:.
239:.
181:.
524::
494:.
490::
401:2
397:)
394:1
388:n
385:(
382:n
359:n
333:2
329:)
326:1
320:n
317:(
314:n
308:=
302:)
297:2
294:n
289:(
266:n
227:2
221:k
169:3
166:=
163:k
145:k
106:k
102:k
98:k
92:k
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
