A fast backtrack algorithm for graph isomorphism (Q1106855)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A fast backtrack algorithm for graph isomorphism |
scientific article; zbMATH DE number 4063116
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A fast backtrack algorithm for graph isomorphism |
scientific article; zbMATH DE number 4063116 |
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
