6 ms·
What is it used for
by vsskanth 6y ago
What is it used for
- j16sdiz 6y agoIt is used for calculate the maximum flow of a flow network. https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Application https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem#Appli...
- PartiallyTyped 6y agoThe max flow is the prime to the min-cut. But you don't use min-cut to find the max flow.
- vmladenov 6y agoI don’t understand the distinction you’re drawing. Can you explain? Max flow and min cut are entirely dual. Which one you use is more a matter of convenience
- PartiallyTyped 6y agoWhat I meant was that if you wish to find the maximum flow, you'd use push-relabel or another max-flow algorithm instead of finding the min-cut first and then building the max-flow solution from there.
- stiar 6y agoWell if you have designated source (s) and sink (t) in a directed network, then yes, finding max s-t flow and min s-t cut are dual problems. Here the paper seems to be dealing with undirected graphs and all cuts in them, not necessarily between a given pair of vertices, so it is slightly different.
- krastanov 6y agoThis is a bit like asking what is matrix diaginalization used for. The applications are much too numerous in many different fields of science and engineering. "Graph partition" problems generally search for ways to separate a graph into subgraphs such that some measure is optimized. E.g. resilience of network connections, immunizations, some error correction algorithms, optimizing flow of stuff through nodes, logistics. This list probably barely scratches the surface. Edit: my comment sounds a bit rude on second read. My apologies, it is the limitations of this medium.
- vsskanth 6y agoThanks. I wasnt being snarky. I really didn't know what such algorithms are used for and the paper didn't mention examples either.
- anticensor 6y agoThis problem is assumed to be common knowledge among graph theory specialists.
- Fordec 6y agoEveryone on Hacker News is not assumed to be graph theory specialists.
- strictfp 6y agoThat's assumed common knowledge for non-graph theory specialists.
- bosswipe 6y agoI would say it's common knowledge for anyone with a CS degree.
- aliahsan07 6y agoits a bit advanced. Many university curriculums just skim through max flow min cut algorithms in a week or two as part of the algorithms class.
- adamnemecek 6y agoIsn’t graph partition a form of diagonalization?
- mehrdadn 6y agoWhat is the relationship? I guess most of us are not spectral graph theory experts. Are you looking at the adjacency matrix or the Laplacian matrix?
- jojobas 6y agoBan half of Twitter accounts so that as little people as possible notice.
- dang 6y ago"Eschew flamebait. Don't introduce flamewar topics unless you have something genuinely new to say. Avoid unrelated controversies and generic tangents." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- Geminidog 6y agoIt's used for passing the interview at a FAANG.
- glglwty 6y agoGraph cut is useful in computer vision.
- petters 6y agoStill used extensively for background-forground segmentation in e.g. Photoshop, I am guessing. Research these days mostly focuses on deep learning though.
- xiphias2 6y agoIt is a fundamental graph problem with many applications in different fields, such as network reliability, where assuming equal failure probability edges, the smallest edge cut in the network has the highest chance to disconnect the network; in VLSI design, where the minimum cut can be used to minimize the number of connections between microprocessor blocks; and as a subproblem in branch-and-cut algorithms for the Traveling Salesman Problem (TSP) and other combinatorial problems. (Copy paste from viecut github repo)
- vsskanth 6y agoThanks.