Results 1 to 10 of about 101,745 (269)
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. R. Ullmann
semanticscholar +5 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
Deepanshu Kush, Benjamin Rossman
semanticscholar +7 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
The Descriptive Complexity of Subgraph Isomorphism without Numerics [PDF]
Theory of Computing Systems, 2016 Let $F$ be a connected graph with $\ell$ vertices. The existence of a subgraph isomorphic to $F$ can be defined in first-order logic with quantifier depth no better than $\ell$, simply because no first-order formula of smaller quantifier depth can ...
Oleg Verbitsky, Maksim Zhukovskii
core +7 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
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
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
Between Subgraph Isomorphism and Maximum Common Subgraph [PDF]
Proceedings of the AAAI Conference on Artificial Intelligence, 2017 When a small pattern graph does not occur inside a larger target graph, we can ask how to find "as much of the pattern as possible" inside the target graph.
Hoffmann, Ruth +2 more
core +3 more sources
Quantum Query Complexity of Subgraph Isomorphism and Homomorphism [PDF]
, 2015 Let $H$ be a fixed graph on $n$ vertices. Let $f_H(G) = 1$ iff the input graph $G$ on $n$ vertices contains $H$ as a (not necessarily induced) subgraph. Let $\alpha_H$ denote the cardinality of a maximum independent set of $H$. In this paper we show: \[
Raghav Kulkarni, Supartha Podder
openalex +5 more sources
Optimized Backtracking for Subgraph Isomorphism [PDF]
International Journal of Database Management Systems, 2012 Subgraph isomorphism is a fundamental graph problem with many important applications. Given two graphs G and SG, the subgraph isomorphism problem is to determine whether G contains a subgraph that is isomorphic to SG. It is well known that the problem is NP complete in the worst case.
Lixin Fu
openalex +2 more sources