Linear matching-time algorithm for the directed graph isomorphism problem

DOI10.1007/BFB0015447MaRDI QIDQ6487989zbMATH OpenFDO

Authors James Jianghai Fu

Publication date 21 March 2023

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

Mathematics Subject Classification ID

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

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

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

Cited in

(2)

• Directed Graph Pattern Matching and Topological Embedding
• 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)