Algorithms for finding directed graph isomorphisms by finite automata

DOI10.1007/BF00982292MaRDI QIDQ3865499zbMATH OpenFDO

Authors Chaochih Yang, Charmane P. May

Publication date 1980

Published in International Journal of Computer & Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00982292

zbMATH Keywords

deterministic state machinefinding directed graph isomorphisms by finite automatagraph isomorphism problemMoore machinenondeterministic state machineworst-case complexity

Mathematics Subject Classification ID

Software, source code, etc. for problems pertaining to combinatorics (05-04) Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A Backtrack Procedure for Isomorphism of Directed Graphs
• A Correction and Some Comments Concerning Graph Isomorphism by Finite Automata
• A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices
• A new algorithm for digraph isomorphism
• An Algorithm for Subgraph Isomorphism
• An Efficient Algorithm for Graph Isomorphism
• Generalized Matrix Functions and the Graph Isomorphism Problem
• Generation of All Closed Partitions on the State Set of a Sequential Machine
• GIT—a heuristic program for testing pairs of directed line graphs for isomorphism
• Graph isomorphism: A heuristic edge-partitioning-oriented algorithm
• scientific article; zbMATH DE number 3493838 (Why is no real title available?)
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• Optimum Featurs and Graph Isomorphism
• Search for a unique incidence matrix of a graph
• Structural Preserving Morphisms of Finite Automata and an Application to Graph Isomorphism
• The Determinant of the Adjacency Matrix of a Graph

This page was built for publication: Algorithms for finding directed graph isomorphisms by finite automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3865499)