Search Space Contraction in Canonical Labeling of Graphs. The individualization-refinement paradigm for computing a canonical labeling and the automorphism group of a graph is investigated. A new algorithmic design aimed at reducing the size of the associated search space is introduced, and a new tool, named ”Traces”, is presented, together with experimental results and comparisons with existing software, such as McKay’s ”nauty”. It is shown that the approach presented here leads to a huge reduction in the search space, thereby making computation feasible for several classes of graphs which are hard for all the main canonical labeling tools in the literature.
Keywords for this software
References in zbMATH (referenced in 3 articles )
Showing results 1 to 3 of 3.
- Bliss, Nathan; Sommars, Jeff; Verschelde, Jan; Yu, Xiangcheng: Solving polynomial systems in the cloud with polynomial homotopy continuation (2015)
- McKay, Brendan D.; Piperno, Adolfo: Practical graph isomorphism. II. (2014)
- Piperno, Adolfo: Search space contraction in canonical labeling of graphs (Preliminary version) (2008) ioport