Graph Isomorphism, Bounded Number of Vertices of Each Color (Graph Isomorphism Problem)
Jump to navigation
Jump to search
Description
Given two colored graphs with the number of vertices of each color bounded, determine whether they are isomorphic to one another.
Related Problems
Generalizations: Graph Isomorphism, General Graphs
Related: Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences, 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 |
|---|---|---|---|---|---|---|
| Babai | 1980 | o(\exp({2}n^{1/2}\log^{2}n)) | $O(n^{2})$ | Exact | Deterministic | Time & Space |
| 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 |
Time Complexity Graph
