On the Complexity of Canonical Labeling of Strongly Regular Graphs

1980/02/01 by László Babai · 6 citations
Computer Science · Engineering · Mathematics · #Graph Labeling and Dimension Problems #Digital Image Processing Techniques #graph theory and CDMA systems #Combinatorics #Mathematics #Computational complexity theory #Graph #Time complexity #Discrete mathematics #Binary logarithm #Algorithm

paper · doi:10.1137/0209018

openalex publication_date 1980/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

We prove that a canonical labeling can be assigned to the n vertices of a strongly regular graph by an algorithm of o(exp (2n^1/2 log ² n)) running time (in the worst case). This complexity, though still not properly subexponential, is much better than O(2ⁿ ).

Citations

• On the ratio of optimal integral and fractional covers

Cited by

• Canonical labeling of graphs
• Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time
• Graph isomorphism problem
• Random subgraphs make identification affordable
• Resolving sets for Johnson and Kneser graphs
• Graph isomorphism problem [wikipedia]