A fast backtrack algorithm for graph isomorphism (Q1106855): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0020-0190(88)90037-3 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W1964028031 / rank | |||
Normal rank | |||
Revision as of 20:28, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A fast backtrack algorithm for graph isomorphism |
scientific article |
Statements
A fast backtrack algorithm for graph isomorphism (English)
0 references
1988
0 references
A backtrack algorithm is described to test two digraphs for isomorphism. Use is made of the degree sequence of vertices and a recursive procedure, using the distance matrices, to obtain the initial partitioning of vertices. The backtrack procedure maps vertices by composing rows and columns of the distance matrix. The algorithm is similar to that given by Schmidt and Druffel (1976) and is much faster than previously known algorithms.
0 references
isomorphism testing
0 references
search tree
0 references
backtrack algorithm
0 references
digraphs
0 references
degree sequence
0 references
recursive procedure
0 references
distance matrices
0 references
initial partitioning of vertices
0 references
