ConceptTheory & Algos
Minimum spanning tree
Given a graph G and edge weights, a minimum spanning tree is a spanning tree of minimum total weight.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Cut and paste argument2Christofides algorithm approximation1Edge contraction1Greedy choice property for minimum spanning trees1Greedy-choice property1IKKBZ algorithm1Induction on m for MST lemma1Kruskal's algorithm1Memoization (caching MST distances)1Minimum spanning tree (MST) lower bound1Minimum spanning tree algorithm1Minimum spanning tree growth lemma1
Lecturers
3Each in their own terms, from the easiest level.
Tom Leighton
The spanning tree of an edge-weighted graph G with the smallest possible sum of edge weights.Amartya Shankha Biswas
A spanning tree of a graph whose edge weight sum is minimized.
Lectures that assume it
2Connections
13The lectures that define it or assume it, and the concepts next to it.