---
res:
  bibo_abstract:
  - 'There is no known polynomial-time algorithm for graph isomorphism testing, but
    elementary combinatorial “refinement” algorithms seem to be very efficient in
    practice. Some philosophical justification for this phenomenon is provided by
    a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
    combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
    classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
    yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
    for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
    assigns labels to vertices in a way that easily permits isomorphism-testing against
    any other graph.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Michael
      foaf_name: Anastos, Michael
      foaf_surname: Anastos
      foaf_workInfoHomepage: http://www.librecat.org/personId=0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  - foaf_Person:
      foaf_givenName: Matthew Alan
      foaf_name: Kwan, Matthew Alan
      foaf_surname: Kwan
      foaf_workInfoHomepage: http://www.librecat.org/personId=5fca0887-a1db-11eb-95d1-ca9d5e0453b3
    orcid: 0000-0002-4003-7567
  - foaf_Person:
      foaf_givenName: Benjamin
      foaf_name: Moore, Benjamin
      foaf_surname: Moore
      foaf_workInfoHomepage: http://www.librecat.org/personId=6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
  bibo_doi: 10.1145/3717823.3718173
  dct_date: 2025^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0737-8017
  - http://id.crossref.org/issn/9798400715105
  dct_language: eng
  dct_publisher: Association for Computing Machinery@
  dct_title: Smoothed analysis for graph isomorphism@
...