
Accession Number : AD0720595
Title : An n log n Algorithm for Isomorphism of Planar Triply Connected Graphs,
Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Personal Author(s) : Hopcroft,John
Report Date : DEC 1970
Pagination or Media Count : 10
Abstract : It is shown that the isomorphism problem for triply connected planar graphs, can be reduced to the problem of minimizing states in a finite automation. By making use of an n log n algorithm for minimizing the number of states in a finite automaton, an algorithm for determing whether two planar triply connected graphs are isomorphic is developed. The asymptotic growth rate of the algorithm grows as n log n where n is the number of vertices in the graph. (Author)
Descriptors : (*GRAPHICS, ALGORITHMS), (*MOLECULAR STRUCTURE, GRAPHICS), DATA PROCESSING, GROUPS(MATHEMATICS), AUTOMATA, THEOREMS
Subject Categories : Theoretical Mathematics
Computer Hardware
Atomic and Molecular Physics and Spectroscopy
Distribution Statement : APPROVED FOR PUBLIC RELEASE