wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

canonical_labeling (436B)


      1 # Canonical labeling
      2 
      3 Labeling a [graph] to be able to test [graph_isomorphism] just by equality
      4 testing of the labels
      5 
      6 https://mathoverflow.net/a/11715
      7 
      8 also called "graph canonization"
      9 
     10 The related problem of computing the [lexicographically_minimal_isomorphic_graph] is [NP_hard]
     11 
     12 See also: [graph_isomorphism], [minimization_automaton], [complete_graph_invariant]
     13 
     14 Up: [graph]
     15 
     16 Aliases: graph canonical labeling, graph canonization