Isomorphism of graphs of bounded valence can be tested in polynomial time

By Eugene M. Luks. 1980

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

Learning Convolutional Neural Networks for Graphs (2016, methodology): “It is known that graph isomorphism is in PTIME for graphs of bounded degree (Luks, 1982).”
The Weisfeiler-Lehman Method and Graph Isomorphism Testing (2011, background): “Efficient GI algorithms do exist for several restricted classes of graphs, such as trees [13], planar graphs [20] and graphs with certain bounded parameters, including valence [22], eigenvalue multiplicity [5] and genus [26].”
Practical graph isomorphism, II (2013, neutral): “These classes include many earlier classes such as graphs of bounded degree (Luks, 1982), bounded genus (Filotti and Mayer, 1980; Miller, 1980) and bounded tree-width (Bod-laender, 1990).”
Isomorphism of Coloured Graphs with Slowly Increasing Multiplicity of Jordan Blocks (1995, background): “There exist polynomial-time algorithms for graphs with bounded degree [10] and for graphs with bounded eigenvalue multiplicity [1].”
Thirty Years Of Graph Matching In Pattern Recognition (2004, unknown): “Lades93[85], Pavlidis95[118], Wiskott97[170], Cho98[26], Duc99[39] Fisher73[51], Kittler89[80], Almohamad93[3], Christamas95[27], Pelillo95 [119], Pelillo95 [120], Gold96[61], Rangarajan96[127], Bomze97[12], Wilson97[167], Pelillo98 [121], Branca99[13], Huet99[71], Medasani99[105], Pelillo99[122, 12”
Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs (2007, background): “To briefly summarize current theoretical knowledge, while no polynomial-time algorithm is known in the context of arbitrary graphs, polynomialtime algorithms are known for numerous restricted families of graphs, including [5, 16, 28, 34], and there is considerable theoretical evidence, including [7,”
Markov Chains on Orbits of Permutation Groups (2012, background): “For graphs with bounded degree the problem is in P [25].”