Access Restriction

Author Unger, Stephen H.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
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.
Description Affiliation: Columbia Univ., New York (Unger, Stephen H.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 7
Issue Number 1
Page Count 9
Starting Page 26
Ending Page 34

Open content in new tab

   Open content in new tab
Source: ACM Digital Library