View source for Graph Isomorphism, Bounded Number of Vertices of Each Color

{{DISPLAYTITLE:Graph Isomorphism, Bounded Number of Vertices of Each Color (Graph Isomorphism Problem)}}
== 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 == 

{| class="wikitable sortable"  style="text-align:center;" width="100%"

! Name !! Year !! Time !! Space !! Approximation Factor !! Model !! Reference

|-

| [[Babai (Graph Isomorphism, Bounded Number of Vertices of Each Color Graph Isomorphism Problem)|Babai]] || 1980 || o(\exp({2}n^{1/2}\log^{2}n)) || $O(n^{2})$ || Exact || Deterministic || [https://epubs.siam.org/doi/10.1137/0209018 Time & Space]
|-
| [[McKay ( Graph Isomorphism Problem)|McKay]] || 1981 || $O((m1 + m2)n^{3} + m2 n^{2} L)$ || ${2}mn+{10}n+m+(m+{4})K+{2}mL$ || Exact || Deterministic || [http://users.cecs.anu.edu.au/~bdm/papers/pgi.pdf Time]
|-
| [[Schmidt & Druffel ( Graph Isomorphism Problem)|Schmidt & Druffel]] || 1976 || $O(n*n!)$ || $O(n^{2})$ || Exact || Deterministic || [https://dl.acm.org/doi/10.1145/321958.321963 Time]
|-
| [[Babai ( Graph Isomorphism Problem)|Babai]] || 2017 || {2}^{$O(\log n)$^3} ||  || Exact || Deterministic || [http://people.cs.uchicago.edu/~laci/update.html, Time]
|-
|}

== Time Complexity Graph == 

[[File:Graph Isomorphism Problem - Graph Isomorphism, Bounded Number of Vertices of Each Color - Time.png|1000px]]