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

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)

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1970
Accession Number
AD0720595

Entities

People

  • John Hopcroft

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Adaptive Control Systems
  • Adaptive Systems
  • Algorithms
  • Automata
  • Automation
  • Control Systems

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Mathematical Modeling and Probability Theory.