|
 ABSTRACT
Given a pair of directed line graphs, the problem of ascertaining whether or not they are isomorphic is one for which no efficient algorithmic solution is known. Since a straightforward enumerative algorithm might require 40 years of running time on a very high speed computer in order to compare two 15-node graphs, a more sophisticated approach seems called for. The situation is similar to that prevailing in areas such as game-playing and theorem-proving, where practical algorithms are unknown (for the interesting cases), but where various practical though only partially successful techniques are available. GIT—Graph Isomorphism Tester—incorporates a variety of processes that attempt to narrow down the search for an isomorphism, or to demonstrate that none exists. No one scheme is relied upon exclusively for a solution, and the program is designed to avoid excessive computation along fruitless lines. GIT has been written in the COMIT language and successfully tested on the IBM 7090.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
YNGVE, V. H. Mechanical Translation of Languages. John Wiley, New York, 1955.
|
| |
2
|
SAMUEL, A. L. Some studies in machine learning using the game of checkers. IBM J. Res. Develop. 7, 59.
|
| |
3
|
ARMSTRONG, D. B. On the efficient assignment of internal codes to sequential machines. IRE-TEC 10, 62.
|
| |
4
|
GELERNTER, H. Realization of a geometry theorem proving machine. UNESCO Conf. Inform. Proc., Paris, 1960.
|
| |
5
|
NEWELL, SHAW, SIMON. Chess playing programs and the problem of complexity. IBM J. Res. Develop. 10, 58.
|
| |
6
|
BERGE, C. The theory of graphs and its applications. John Wiley and Sons, 1962.
|
| |
7
|
YNGVE, V. H., et al. An Introduction to COMIT Programming. MIT Press, 1962.
|
 |
8
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3