On construction and identification of graphs

By B. Weisfeiler. 1976

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

Graph Invariant Kernels (2015, methodology): “The 1-dimensional Weisfeiler-Lehman (WL) refinement algorithm [Weisfeiler, 1976] finds a partition of the vertices of a graph in an iterative fashion: • Initialization: All colors are initialized using vertex labels, i.e. ∀v ∈ V L(0)(v) .= `d(v) • Recoloring step: ∀v ∈ V L(t+1)(v) = id({L(t)(w)|w ∈…”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “Theory The Weisfeiler-Leman algorithm constitutes one of the earliest approaches to isomorphism testing [110, 111], having been heavily investigated by the theory community over the last few decades [49].”
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, background): “The algorithm stops when the set of labels stabilizes, meaning that no new diierences between vertices are discovered.”
Non-Isomorphic Graphs with Cospectral Symmetric Powers (2009, background): “Suppose that X is a union of fibers of [G].”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, background): “, [35, 34], and has been heavily investigated in the theory community.”