View source for Graph Isomorphism, Bounded Vertex Valences

{{DISPLAYTITLE:Graph Isomorphism, Bounded Vertex Valences (Graph Isomorphism Problem)}}
== 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 == 

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

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

|-

| [[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.ezproxy.canberra.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.ezproxy.canberra.edu.au/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]
|-
| [[Babai 1980 (Graph Isomorphism, Bounded Vertex Valences Graph Isomorphism Problem)|Babai]] || 1980 || \exp(n^{\frac{1}{2} + $O({1})$}) || $O(n^{2})$ || Exact || Randomized || [https://epubs-siam-org.ezproxy.canberra.edu.au/doi/10.1137/0209018 Time] & [https://epubs-siam-org.ezproxy.canberra.edu.au/doi/epdf/10.1137/0209018 Space]
|-
|}