ConceptTheory & Algos
Vertex cover
A set of vertices that intersects or meets all the edges in the graph.
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.
2-Approximation algorithm12-Approximation algorithm for vertex cover1Approx-VertexCover1Bounded-degree graph kernel bound1Bounded-search-tree algorithm1Brute-force algorithm for vertex cover1Integer linear program1Kernelization1Koenig's theorem1König's theorem1Maximum degree heuristic1Polynomial kernel for vertex cover1
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
A subset of vertices that touch all edges of a graph.Srini Devadas
A set of vertices in an undirected graph that includes at least one endpoint of every edge in the graph.
Lectures that assume it
2Connections
14The lectures that define it or assume it, and the concepts next to it.