Graph Isomorphism, General Graphs: Difference between revisions

From Algorithm Wiki
Jump to navigation Jump to search
(Created page with "{{DISPLAYTITLE:Graph Isomorphism, General Graphs (Graph Isomorphism Problem)}} == Description == Given two graphs, determine whether they are isomorphic to one another. == Related Problems == Subproblem: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences, Largest Common Subtree Related: Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Ve...")
 
No edit summary
Line 12: Line 12:
== Parameters ==  
== Parameters ==  


<pre>$n$: number of vertices in the larger graph</pre>
$n$: number of vertices in the larger graph


== Table of Algorithms ==  
== Table of Algorithms ==  

Revision as of 13:03, 15 February 2023

Description

Given two graphs, determine whether they are isomorphic to one another.

Related Problems

Subproblem: Graph Isomorphism, Bounded Number of Vertices of Each Color, Graph Isomorphism, Trivalent Graphs, Graph Isomorphism, Bounded Vertex Valences, Largest Common Subtree

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 and Luks 1983 \exp(n^{\frac{1}{2} + o({1})}) Exact Deterministic Time
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

Graph Isomorphism Problem - Graph Isomorphism, General Graphs - Time.png