Results 1 to 10 of about 102,063 (249)
An Algorithm for Subgraph Isomorphism [PDF]
Journal of the ACM, 1976 Subgraph isomorphism can be determined by means of a brute-force tree-search enumeration procedure. In this paper a new algorithm is introduced that attains efficiency by inferentially eliminating successor nodes in the tree search. To assess the time actually taken by the new algorithm, subgraph isomorphism, clique detection, graph isomorphism, and ...
J. Ullmann
semanticscholar +6 more sources
Tree-depth and the Formula Complexity of Subgraph Isomorphism [PDF]
SIAM Journal on Computing, 2020 For a fixed “pattern” graph $G$, the colored $G$-subgraph isomorphism problem (denoted $\text{SUB}(G)$) asks, given an $n$-vertex graph $H$ and a coloring $V(H)\rightarrow V(G)$, whether $H$ contains a properly colored copy of $G$. The complexity of this
D. Kush, Benjamin Rossman
semanticscholar +7 more sources
Efficient Large-Scale IoT Botnet Detection through GraphSAINT-Based Subgraph Sampling and Graph Isomorphism Network [PDF]
MathematicsIn recent years, with the rapid development of the Internet of Things, large-scale botnet attacks have occurred frequently and have become an important challenge to network security.
Lihua Yin +3 more
doaj +3 more sources
On the First-Order Complexity of Induced Subgraph Isomorphism [PDF]
Logical Methods in Computer Science, 2019 Given a graph $F$, let $I(F)$ be the class of graphs containing $F$ as an induced subgraph. Let $W[F]$ denote the minimum $k$ such that $I(F)$ is definable in $k$-variable first-order logic.
Oleg Verbitsky, Maksim Zhukovskii
doaj +8 more sources
HyGraph: a subgraph isomorphism algorithm for efficiently querying big graph databases
Journal of Big Data, 2022 The big graph database provides strong modeling capabilities and efficient querying for complex applications. Subgraph isomorphism which finds exact matches of a query graph in the database efficiently, is a challenging problem.
Merve Asiler, Adnan Yazıcı, Roy George
doaj +2 more sources
The Glasgow Subgraph Solver: Using Constraint Programming to Tackle Hard Subgraph Isomorphism Problem Variants [PDF]
Graph Transformation13th International Conference, 2020 The Glasgow Subgraph Solver provides an implementation of state of the art algorithms for subgraph isomorphism problems. It combines constraint programming concepts with a variety of strong but fast domain-specific search and inference techniques, and is
McCreesh C, Prosser P, Trimble J.
europepmc +2 more sources
An Efficient Subgraph Isomorphism Solver for Large Graphs
IEEE Access, 2021 For a given pair of pattern and data graphs, the subgraph isomorphism finding problem locates all instances of the pattern graph into the data graph. For a given subgraph isomorphic image of the pattern graph in a data graph, the set of all ordered pairs
Zubair Ali Ansari +2 more
doaj +2 more sources
DotMotif: an open-source tool for connectome subgraph isomorphism search and graph queries [PDF]
Scientific Reports, 2021 Recent advances in neuroscience have enabled the exploration of brain structure at the level of individual synaptic connections. These connectomics datasets continue to grow in size and complexity; methods to search for and identify interesting graph ...
Jordan K. Matelsky +6 more
doaj +2 more sources
TemporalRI: subgraph isomorphism in temporal networks with multiple contacts
Applied Network Science, 2021 Temporal networks are graphs where each edge is associated with a timestamp denoting when two nodes interact. Temporal Subgraph Isomorphism (TSI) aims at retrieving all the subgraphs of a temporal network (called target) matching a smaller temporal ...
Giovanni Micale +3 more
doaj +2 more sources
AllDifferent-based filtering for subgraph isomorphism [PDF]
Artificial Intelligence, 2010 AbstractThe subgraph isomorphism problem involves deciding if there exists a copy of a pattern graph in a target graph. This problem may be solved by a complete tree search combined with filtering techniques that aim at pruning branches that do not contain solutions. We introduce a new filtering algorithm based on local all different constraints.
Christine Solnon
openalex +4 more sources