A fast backtrack algorithm for graph isomorphism (Q1106855)
From MaRDI portal
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
0 references
