作者: Stephen H. Unger
关键词:
摘要: Given a pair of directed line graphs, the problem ascertaining whether or not they are isomorphic is one for which no efficient algorithmic solution known. Since straightforward enumerative algorithm might require 40 years running time on very high speed computer in order to compare two 15-node more sophisticated approach seems called for. The situation similar that prevailing areas such as game-playing and theorem-proving, where practical algorithms unknown (for interesting cases), but various though only partially successful techniques available. GIT—Graph Isomorphism Tester—incorporates variety processes attempt narrow down search an isomorphism, demonstrate none exists. No scheme relied upon exclusively solution, program designed avoid excessive computation along fruitless lines. GIT has been written COMIT language successfully tested IBM 7090.