Premium
Backtrack search algorithms and the maximal common subgraph problem
Author(s) -
McGregor James J.
Publication year - 1982
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380120103
Subject(s) - pruning , variety (cybernetics) , computer science , algorithm , breadth first search , search algorithm , component (thermodynamics) , subgraph isomorphism problem , theoretical computer science , artificial intelligence , graph , physics , agronomy , biology , thermodynamics
Backtrack algorithms are applicable to a wide variety of problems. An efficient but readable version of such an algorithm is presented and its use in the problem of finding the maximal common subgraph of two graphs is described. Techniques available in this application area for ordering and pruning the backtrack search are discussed. This algorithm has been used successfully as a component of a program for analysing chemical reactions and enumerating the bond changes which have taken place.