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 165 articles , 1 standard article )

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

1 2 3 ... 7 8 9 next

  1. Chang, Mun See; Jefferson, Christopher: Disjoint direct product decompositions of permutation groups (2022)
  2. Dokuchaev, Mikhailo; Mandel, Arnaldo; Plakhotnyk, Makar: The cone of quasi-semimetrics and exponent matrices of tiled orders (2022)
  3. Turcotte, Jérémie: Cops and robbers on (2K_2)-free graphs (2022)
  4. Xu, Si-Ao; Li, Yun-Xiang; Hua, Hongbo; Pan, Xiang-Feng: On the resistance diameters of graphs and their line graphs (2022)
  5. Araujo-Pardo, G.; Dalfó, C.; Fiol, M. A.; López, N.: Bipartite biregular Moore graphs (2021)
  6. Araya, Makoto; Harada, Masaaki; Saito, Ken: Characterization and classification of optimal LCD codes (2021)
  7. Azam, Naveed Ahmed; Shurbevski, Aleksandar; Nagamochi, Hiroshi: A method for enumerating pairwise compatibility graphs with a given number of vertices (2021)
  8. Bausch, Johannes; Leditzky, Felix: Error thresholds for arbitrary Pauli noise (2021)
  9. DeBiasio, Louis; Lo, Allan; Molla, Theodore; Treglown, Andrew: Transitive tournament tilings in oriented graphs with large minimum total degree (2021)
  10. Dias, Gustavo; Liberti, Leo: Exploiting symmetries in mathematical programming via orbital independence (2021)
  11. Dickinson, Peter J. C.; de Zeeuw, Reinier: Generating irreducible copositive matrices using the stable set problem (2021)
  12. Dubinsky, Manuel; Massri, César; Taubin, Gabriel: Minimum spanning tree cycle intersection problem (2021)
  13. Fabrici, Igor; Madaras, Tomáš; Timková, Mária; Van Cleemput, Nico; Zamfirescu, Carol T.: Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian (2021)
  14. Ganzhinov, Mikhail; Szöllősi, Ferenc: Biangular lines revisited (2021)
  15. Gorla, Daniele; Salvo, Ivano: Conflict vs causality in event structures (2021)
  16. Gruen, Angus; Morrison, Scott: Computing modular data for pointed fusion categories (2021)
  17. Jayawardene, Chula J.; Narváez, David; Radziszowski, Stanisław: Star-critical Ramsey numbers for cycles versus (K_4) (2021)
  18. Jefferson, Christopher; Pfeiffer, Markus; Wilson, Wilf A.; Waldecker, Rebecca: Permutation group algorithms based on directed graphs (2021)
  19. Krčadinac, Vedran: A new partial geometry (\mathrmpg(5,5,2)) (2021)
  20. Peitl, Tomáš; Szeider, Stefan: Finding the hardest formulas for resolution (2021)

1 2 3 ... 7 8 9 next