Graph Isomorphism, Bounded Vertex Valences (Graph Isomorphism Problem)
Jump to navigation
Jump to search
Description
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
Parameters
$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 |