ConceptTheory & Algos
Graph isomorphism problem
The computational problem of determining whether two finite graphs are isomorphic, meaning one can be transformed into the other by permuting its vertices.
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.
Lecturers
3Each in their own terms, from the easiest level.
Ryan O'Donnell
Given two graphs, determine if they are isomorphic, meaning one can be transformed into the other by permuting vertex labels.Colva Roney-Dougal
The graph isomorphism problem asks whether two graphs are the same, just with different vertex names and drawn differently.Michael Sipser
Testing whether two graphs are permutations of one another, which is in NP but not known to be in P.
Connections
8The lectures that define it or assume it, and the concepts next to it.