The subgraph isomorphism problem for outerplanar graphs
Theoretical Computer Science, 1982 AbstractThis paper deals with the subgraph isomorphism problem for outerplanar graphs (SUBOUTISOM). In general, since trees and forests are outerplanar, SUBOUTISOM is NP-complete. We show that SUBOUTISOM remains NP-complete even when the strongest connectivity requirements are imposed on both graphs.
openaire +2 more sources
Subgraph Matching Kernels for Attributed Graphs [PDF]
, 2012 We propose graph kernels based on subgraph matchings, i.e. structure-preserving bijections between subgraphs. While recently proposed kernels based on common subgraphs (Wale et al., 2008; Shervashidze et al., 2009) in general can not be applied to ...
Kriege, Nils, Mutzel, Petra
core
When Subgraph Isomorphism is Really Hard, and Why This Matters for Graph Databases
Journal of Artificial Intelligence Research, 2018 The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not.
Ciaran McCreesh +3 more
semanticscholar +1 more source
cmFSM: a scalable CPU-MIC coordinated drug-finding tool by frequent subgraph mining
BMC Bioinformatics, 2018 Background Frequent subgraphs mining is a significant problem in many practical domains. The solution of this kind of problem can particularly used in some large-scale drug molecular or biological libraries to help us find drugs or core biological ...
Shunyun Yang +6 more
doaj +1 more source
Homology analysis of malware based on graph
Tongxin xuebao, 2017 Malware detection and homology analysis has been the hotspot of malware analysis.API call graph of malware can represent the behavior of it.Because of the subgraph isomorphism algorithm has high complexity,the analysis of malware based on the graph ...
Bing-lin ZHAO +4 more
doaj +2 more sources
Instruction Scheduling Based on Subgraph Isomorphism for a High Performance Computer Processor [PDF]
, 2008 Ricardo Santos +2 more
openalex +1 more source
Practical Bigraphs via Subgraph Isomorphism - Benchmark Instances
, 2021 Blair Archibald +3 more
openalex +4 more sources
A virtual network mapping algorithm based on subgraph isomorphism detection [PDF]
, 2009 Jens Lischka, Holger Karl
openalex +1 more source
Random Generation Topology Coding Technique in Asymmetric Topology Encryption
MathematicsThe security of traditional public key cryptography algorithms depends on the difficulty of the underlying mathematical problems. Asymmetric topological encryption is a graph-dependent encryption algorithm produced to resist attacks by quantum computers ...
Jing Su, Bing Yao
doaj +1 more source
Speeding up the Detection of Adsorbate Lateral Interactions in Graph-Theoretical Kinetic Monte Carlo Simulations. [PDF]
J Phys Chem A, 2023 Benson RL, Yadavalli SS, Stamatakis M.
europepmc +1 more source