An Algorithm for Subgraph Isomorphism

By J. Ullmann. 1976

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Graph Based Shapes Representation and Recognition (2007, methodology): “A comparison of frequently used algorithms i.e., best backtracking methods [ 8 ] [9], a group theory based Naughty algorithm [10], VF algorithm and VF2 algorithm [11] is given in [12].”
A Path Following Algorithm for the Graph Matching Problem (2008, methodology): “Another group of methods includes approximate algorithms which are supposed to be more scalable.”
Factorized Graph Matching (2016, background): “Early works [19], [20], [21] on GM often treated the problem as a special case of (sub)graph isomorphism, where the graphs are binary and an exact matching between nodes and edges is of interest.”
TALE: A Tool for Approximate Large Graph Matching (2008, methodology): “The database community has had a long-standing interest in querying graph databases [6], [9], [13], [15], [17]–[22].”
Foundations of Modern Query Languages for Graph Databases (2016, background): “…terms, where these latter two matches would be dropped; in other words it may be desirable to restrict h to be an injective (i.e., one-to-one) mapping, in which case the matching process corresponds to the well-known notion of subgraph isomorphism (see, e.g., Ullmann (1976) and Fan (2012)).”
Pharmacophore modeling and applications in drug discovery: challenges and recent advances. (2010, methodology): “com 40 Ullmann, J.R. (1976) An algorithm for subgraph isomorphism.”
Efficient Subgraph Matching on Billion Node Graphs (2012, methodology): “For example, Ullmann [26] and Cordella et al [11] proposed global pruning strategy to accelerate query processing.”
An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases (2012, background): “Ullmann [14] proposes the ﬁrst practical algorithm for subgraph isomorphism search for graphs.”
Closure-Tree: An Index Structure for Graph Queries (2006, methodology): “We use Ullmann’s algorithm [22] for exact subgraph isomorphism.”
Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting (2020, background): “In addition, arbitrary subgraph counting/enumeration is widely studied, and many general-purpose algorithms [51], TABLE 1 Graph Classification Accuracy on TUD Dataset.”
Frequent subgraph discovery (2001, methodology): “A well-known algorithm for subgraph isomorphism is proposed in [22].”
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking (2007, methodology): “We developed this technique for subgraph isomorphism independently, but subsequently identified a prior use [23].”
BinHunt: Automatically Finding Semantic Differences in Binary Programs (2008, background): “However, it is widely accepted that the problem of exact subgraph isomorphism, which is a special case of common subgraph isomorphism with the requirement that the resulting common subgraph coincides with one of the input graphs, is much more efficiently solved by the backtracking algorithm [8,13].”