The graph isomorphism disease

By R. Read, Derek Gordon Corneil. 1977

How researchers see this paper

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

In Algorithms & Complexity

Citations in the corpus

The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, methodology): “The general type of method labelled as iterative vertex classification is discussed in [29] and [32].”
Covariant Compositional Networks For Learning Graphs (2018, background): “However, it’s interesting to note that the Weisfeiler– Lehmann isomorphism test essentially builds on just this formula, with a speciﬁc choice of Υ (Read & Corneil, 1977).”
Practical graph isomorphism, II (2013, neutral): “GI has long been a favorite target of algorithm designers—so much so that it was already described as a “disease” in 1976 (Read and Corneil, 1977).”
A Tree-Based Kernel for Graphs (2012, background): “For example, a total order between DAG vertices would require an algorithm with GI-complete computational complexity [17].”
Frequent subgraph discovery (2001, methodology): “To narrow down the search space, we first partition the vertices by their degrees and labels, which is a well-known technique called vertex invariants [ 18 ].”
Graph-based mining of multiple object usage patterns (2009, background): “A state-of-the-art algorithm for checking graph isomorphism is canonical labeling [26], which works well with sparse graphs, but not with dense graphs.”
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, background): “…a polynomial-time algorithm for the graph isomorphism problem—the problem of deciding whether two given graphs are the same up to a change of labels—which from a theoretical perspective ranks among the most extensively studied computational problems [2] [3] [4] [18] [19] [24] [36] [39].”
An optimal lower bound on the number of variables for graph identification (1992, methodology): “An old basic idea in graph isomorphism testing and canonical labeling is the naive vertex classification algorithm as described in Read and Corneil [ 37 ].”
VUDDY: A Scalable Approach for Vulnerable Code Clone Discovery (2017, background): “Such tree-based approaches require extensive execution time, as the subgraph isomorphism problem is a well-known and time-consuming NP-Complete problem [28].”
Computational Generation of Referring Expressions: A Survey (2012, background): “The informal notion of one graph being “placed over” another corresponds with a subgraph isomorphism (Read and Corneil 1977).”
A survey of frequent subgraph mining algorithms (2012, methodology): “To further reduce the computation resulting from the permutations of the matrix, canonical labellings are usually compressed, using what is known as a vertex invariant scheme (Read & Corneil 1977), that allows the content of an adjacency matrix to be partitioned according to the vertex labels.”
Finding Frequent Patterns in a Large Sparse Graph* (2004, background): “Such a code is referred to as the canonical label of a graph G = (V, E) (Read and Corneil, 1977; Fortin, 1996), and we will denote it by cl(G).”