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