Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Cut (graph theory)

Related lectures (28)

Max-flow Min-cut Theorem

Explores the equivalence between maximum flow and minimum cut in network theory, demonstrating its applications through examples and edge-disjoint paths.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

Discusses the Ford-Fulkerson method and strongly connected components in graph algorithms.

Stein Algorithm: Polynomial Identity Testing

Explores the Stein algorithm for polynomial identity testing and the minimization of a cut problem.

Submodular Function Minimization

Covers submodular functions and their minimization, emphasizing diminishing returns and the Lovász Extension.

Clustering: K-means & LDA

Covers clustering using K-means and LDA, PCA, K-means properties, Fisher LDA, and spectral clustering.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Semidefinite Programming: Formulations and Applications

Explores Semidefinite Programming formulations, SDP relaxations, and optimization strategies with convergence guarantees.

Max Flav-Min Cut in Directed Graphs

Covers the concept of maximum flow-minimum cut in directed graphs with capacity constraints.

Primal-dual Optimization II

Explores primal-dual optimization methods, focusing on Lagrangian approaches and various methods like penalty, augmented Lagrangian, and splitting techniques.

Maximum Flow: Theory and Applications

Explores maximum flow in graphs, covering Ford-Fulkerson algorithm, flow conservation, and minimum cut.

Sparsest Cut: Bourgain's Theorem Log in to Mediaspace to watch this video

Explores Bourgain's theorem on sparsest cut in graphs, emphasizing semimetrics and cut optimization.

Ford-Fulkerson Method: Max Flow and Min Cut Log in to Mediaspace to watch this video

Explores the Ford-Fulkerson method for finding max flow and min cut in a network.

Ford-Fulkerson Method Log in to Mediaspace to watch this video

Introduces the Ford-Fulkerson Method to find the maximum flow in a network.

Low Diameter Random Partitioning Log in to Mediaspace to watch this video

Discusses Low Diameter Randomized Decomposition and graph partitioning for edge cuts and coloring.

Cheeger's Inequality Log in to Mediaspace to watch this video

Explores Cheeger's inequality and its implications in graph theory.

Shape From Stereo-2 Log in to Mediaspace to watch this video

Explores stereo vision concepts such as occlusions, window size impact, multi-view stereo, dynamic shape reconstruction, and graph-based segmentation.

Segmentation: Theory and Algorithms Log in to Mediaspace to watch this video

Covers the theory and algorithms behind image segmentation, focusing on region identification and evaluation.

Semi-Definite Programming Log in to Mediaspace to watch this video

Covers semi-definite programming and optimization over positive semidefinite cones.

Graph Sketching: Connected Components Log in to Mediaspace to watch this video

Covers graph sketching and connected components in streaming models.

Max-Flow Problem: Ford-Fulkerson Algorithm Log in to Mediaspace to watch this video

Explores the Ford-Fulkerson algorithm for solving the Max-Flow problem and its applications in network flow optimization.