Graph Isomorphism, Bounded Vertex Valences (Graph Isomorphism Problem)

From Algorithm Wiki
Jump to navigation Jump to search


Given two graphs with the degree of each vertex bounded, determine whether they are isomorphic to one another.

Related Problems

Generalizations: Graph Isomorphism, General Graphs

Related: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Largest Common Subtree, Subtree Isomorphism


$n$: number of vertices in the larger graph

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
McKay 1981 $O((m1 + m2)n^{3} + m2 n^{2} L)$ ${2}mn+{10}n+m+(m+{4})K+{2}mL$ Exact Deterministic Time
Schmidt & Druffel 1976 $O(n*n!)$ $O(n^{2})$ Exact Deterministic Time
Babai 2017 {2}^{$O(\log n)$^3} Exact Deterministic Time
Babai 1980 \exp(n^{\frac{1}{2} + $O({1})$}) $O(n^{2})$ Exact Randomized Time & Space