BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-11350@prod.cs.cornell.edu
DTSTAMP:20201005T202000Z
DTSTART:20201005T202000Z
DTEND:20201005T212000Z
SUMMARY:Theory Seminar: Computing (All) Minimum Cuts In Practice
DESCRIPTION:Darren Strash, Hamilton College. Computing (All) Minimum Cuts In Practice (via Zoom)Abstract: The minimum cut problem is the problem of computing a partition of a graph's vertices into two sets (i.e., a cut) to minimize the number of edges crossing the cut. In this talk, I present a practically efficient algorithm to find all global minimum cuts in huge undirected graphs. While the problem is easily solved in polynomial time in theory, previous techniques are too slow to be used on large graphs in practice: $O(nm +n^2\log n +n^*m\log n)$, where $n$ is the number of vertices of the graph, $m$ is the number of edges, and $n^*$ is the number of vertices in a cactus representation of all minimum cuts. Our new algorithm is the conclusion of a series of recent results focusing on computing minimum cuts efficiently in practice. I give an overview of these recent results, showing the evolution to the present algorithm for efficiently computing all minimum cuts.The techniques used have the...https://prod.cs.cornell.edu/content/theory-seminar-computing-all-minimum-cuts-practice
LOCATION:Streaming via Zoom
END:VEVENT
END:VCALENDAR