Graph Isomorphism, Trivalent Graphs: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Graph Isomorphism, Trivalent Graphs (Graph Isomorphism Problem)}} == 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,...") |
No edit summary |
||
| Line 12: | Line 12: | ||
== Parameters == | == Parameters == | ||
$n$: number of vertices in the larger graph | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 12:03, 15 February 2023
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 |