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.

References in zbMATH (referenced in 180 articles , 1 standard article )

Showing results 1 to 20 of 180.
Sorted by year (citations)

1 2 3 ... 7 8 9 next

  1. Aboulker, Pierre; Havet, Frédéric; Knauer, Kolja; Rambaud, Clément: On the dichromatic number of surfaces (2022)
  2. Al-Yakoob, Salem; Stevanović, Dragan: On stepwise transmission irregular graphs (2022)
  3. Brinkmann, Gunnar; Goedgebeur, Jan; Mckay, Brendan D.: The minimality of the Georges-Kelmans graph (2022)
  4. Bruns, Winfried: Automorphism groups and normal forms in Normaliz (2022)
  5. Cameron, Ben; Hoàng, Chính T.; Sawada, Joe: Dichotomizing (k)-vertex-critical (H)-free graphs for (H) of order four (2022)
  6. Chang, Mun See; Jefferson, Christopher: Disjoint direct product decompositions of permutation groups (2022)
  7. Dokuchaev, Mikhailo; Mandel, Arnaldo; Plakhotnyk, Makar: The cone of quasi-semimetrics and exponent matrices of tiled orders (2022)
  8. Goedgebeur, Jan; Van Overberghe, Steven: New bounds for Ramsey numbers (R ( K_k - e , K_l - e )) (2022)
  9. Kiefer, Sandra; Neuen, Daniel: The power of the Weisfeiler-Leman algorithm to decompose graphs (2022)
  10. Kurz, Sascha: On the number of minimal codewords in codes generated by the adjacency matrix of a graph (2022)
  11. Turcotte, Jérémie: Cops and robbers on (2K_2)-free graphs (2022)
  12. Xu, Si-Ao; Li, Yun-Xiang; Hua, Hongbo; Pan, Xiang-Feng: On the resistance diameters of graphs and their line graphs (2022)
  13. Yan, Zhidan; Wang, Wei: The smallest pair of cospectral cubic graphs with different chromatic indexes (2022)
  14. Araujo-Pardo, G.; Dalfó, C.; Fiol, M. A.; López, N.: Bipartite biregular Moore graphs (2021)
  15. Araya, Makoto; Harada, Masaaki; Saito, Ken: Characterization and classification of optimal LCD codes (2021)
  16. Azam, Naveed Ahmed; Shurbevski, Aleksandar; Nagamochi, Hiroshi: A method for enumerating pairwise compatibility graphs with a given number of vertices (2021)
  17. Bausch, Johannes; Leditzky, Felix: Error thresholds for arbitrary Pauli noise (2021)
  18. da Silva, Celso M. jun.; Del-Vecchio, Renata R.; Monteiro, Bruno B.: Relating centralities in graphs and the principal eigenvector of its distance matrix (2021)
  19. DeBiasio, Louis; Lo, Allan; Molla, Theodore; Treglown, Andrew: Transitive tournament tilings in oriented graphs with large minimum total degree (2021)
  20. de Souza Maceira Belay, Diego; de Freitas, Maria Aguieiras A.; da Silva, Celso M. jun.: On trees with algebraic connectivity greater than or equal to (2(1-\cos(\frac\pi7))) (2021)

1 2 3 ... 7 8 9 next