Linear matching-time algorithm for the directed graph isomorphism problem

DOI10.1007/BFB0015447MaRDI QIDQ6487989zbMATH OpenFDO

Authors James Jianghai Fu

Publication date 21 March 2023

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Nonnumerical algorithms (68W05)

Recommendations

• Directed Graph Pattern Matching and Topological Embedding
• scientific article; zbMATH DE number 2102042
• Strings, trees, and patterns
• Isomorphism testing via polynomial-time graph extensions
• An Algorithm Portfolio for the Sub-graph Isomorphism Problem

Cites work

• scientific article; zbMATH DE number 125890 (Why is no real title available?)
• A note on the subtree isomorphism for ordered trees and related problems
• Depth-First Search and Linear Graph Algorithms
• On the subtree isomorphism problem for ordered trees
• Pattern Matching in Trees
• Term rewriting in \(\mathrm{CT}_\Sigma \)

Cited in

(1)

• Bypass strong V-structures and find an isomorphic labelled subgraph in linear time

This page was built for publication: Linear matching-time algorithm for the directed graph isomorphism problem

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