Accession Number:

AD0720595

Title:

An n log n Algorithm for Isomorphism of Planar Triply Connected Graphs,

Descriptive Note:

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1970-12-01

Pagination or Media Count:

10.0

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

Subject Categories:

  • Theoretical Mathematics
  • Computer Hardware
  • Atomic and Molecular Physics and Spectroscopy

Distribution Statement:

APPROVED FOR PUBLIC RELEASE