Graph Isomorphism, Trivalent Graphs (Graph Isomorphism Problem)

From Algorithm Wiki
Jump to navigation Jump to search

Description

Given two trivalent graphs (AKA cubic graphs--graphs in which each vertex has degree 3), 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, 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
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