Combinatorial Optimization
Explore discrete structures; network algorithms; complexity and approximations. Concepts and connections are available independently of video coverage.
FOLLOW AN IDEA
Bipartite matching
Matching in a two-part graph pairs vertices across parts without shared endpoints.
Explore concept graph · Explore connected videos
Different ways to understand it
No reviewed video yet. Explore the concept in a map or suggest a resource. Suggest a video
More concepts to explore
Assignment problem
A costed one-to-one pairing can be optimized using matching or linear programming structure.
Graph matchings
A matching is a set of edges with no shared endpoints.
Max-flow min-cut theorem
For a finite capacitated network, the maximum flow value equals minimum separating cut capacity.
Network flow models
Maximise flow through capacities; the min-cut theorem turns a bottleneck argument into a computable bound.
Approximation algorithms
An approximation algorithm provides a provable ratio to the optimum under stated assumptions.
Knowledge connections
- Max-flow min-cut theorem · Related · Map context
- Assignment problem · Related · Map context
- Graph matchings · Prerequisite · Map context
- Graph matchings · Related · Map context
- Network flow models · Related · Map context
Appears in these maps
Graph Theory
Explore graph structures; paths, coloring and planarity; networks and spectral viewpoints. Concepts and connections are available independently of video coverage.