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

1982/08/01 by Eugene M. Luks · 373 citations
Computer Science · Engineering · Mathematics · #Automorphism #Automorphism group #Bounded function #Coding theory and cryptography #Combinatorics #Discrete mathematics #Finite Group Theory Research #Graph #Graph isomorphism #Isomorphism (crystallography) #Mathematics #Permutation (music) #Permutation group #graph theory and CDMA systems

paper · pdf · doi:10.1016/0022-0000(82)90009-5

published in Journal of Computer and System Sciences 25(1), 42-65 (Elsevier BV)

crossref issued 1982/08/01 · crossref published 1982/08/01 · crossref published-print 1982/08/01 · openalex publication_date 1982/08/01 · crossref created 2003/12/04 · crossref deposited 2019/02/16 · openalex created_date 2025/10/10 · crossref indexed 2026/06/20 · openalex updated_date 2026/08/02

Citations

• Finite Permutation Groups and Finite Simple Groups

Cited by

• On the Complexity of Polytope Isomorphism Problems
• Homeomorphism of 2-Complexes is Graph Isomorphism Complete
• Computational complexity and the classification of finite simple groups
• Canonical labeling of graphs
• Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time
• Graph isomorphism problem
• Graph isomorphism is low for PP
• Subexponential Algorithms for Unique Games and Related Problems
• A (sub)graph isomorphism algorithm for matching large graphs
• Graph Isomorphism for (H₁,H₂)-free Graphs: An Almost Complete Dichotomy
• A spectral assignment approach for the graph isomorphism problem
• Practical graph isomorphism, II
• The Space Complexity of k-Tree Isomorphism
• Graph isomorphism problem [wikipedia]