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

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

1 2 3 ... 6 7 8 next

  1. Araya, Makoto; Harada, Masaaki; Saito, Ken: Characterization and classification of optimal LCD codes (2021)
  2. DeBiasio, Louis; Lo, Allan; Molla, Theodore; Treglown, Andrew: Transitive tournament tilings in oriented graphs with large minimum total degree (2021)
  3. Dias, Gustavo; Liberti, Leo: Exploiting symmetries in mathematical programming via orbital independence (2021)
  4. Dickinson, Peter J. C.; de Zeeuw, Reinier: Generating irreducible copositive matrices using the stable set problem (2021)
  5. Dubinsky, Manuel; Massri, César; Taubin, Gabriel: Minimum spanning tree cycle intersection problem (2021)
  6. 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)
  7. Gorla, Daniele; Salvo, Ivano: Conflict vs causality in event structures (2021)
  8. Jayawardene, Chula J.; Narváez, David; Radziszowski, Stanisław: Star-critical Ramsey numbers for cycles versus (K_4) (2021)
  9. Xu, Kexiang; Ilić, Aleksandar; Iršič, Vesna; Klavžar, Sandi; Li, Huimin: Comparing Wiener complexity with eccentric complexity (2021)
  10. Abrosimov, Mikhaĭl Borisovich; Sudani, Hayder Hussein Karim; Lobov, Aleksandr Andreevich: Construction of all minimal edge extensions of the graph with isomorphism rejection (2020)
  11. Adams, Peter; El-Zanati, Saad I.; Florido, Peter; Turner, William: On 2- and 3-factorizations of complete 3-uniform hypergraphs of order up to 9 (2020)
  12. Alemany-Puig, Lluís; Ferrer-I-Cancho, Ramon: Edge crossings in random linear arrangements (2020)
  13. Araya, Makoto; Harada, Masaaki: On the minimum weights of binary linear complementary dual codes (2020)
  14. Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg: On Weisfeiler-Leman invariance: subgraph counts and related graph properties (2020)
  15. Banks, Peter; Panzer, Erik; Pym, Brent: Multiple zeta values in deformation quantization (2020)
  16. Berčič, Katja; Vidali, Janoš: DiscreteZOO: a fingerprint database of discrete objects (2020)
  17. Bernstein, Daniel Irving; Farnsworth, Cameron; Rodriguez, Jose Israel: The algebraic matroid of the finite unit norm tight frame (funtf) variety (2020)
  18. Bian, Zhengbing; Chudak, Fabian; Macready, William; Roy, Aidan; Sebastiani, Roberto; Varotti, Stefano: Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results (2020)
  19. Bikov, Aleksandar; Nenov, Nedyalko: On the independence number of ((3,3))-Ramsey graphs and the Folkman number (F_e(3,3;4)) (2020)
  20. Bright, Curtis; Cheung, Kevin; Stevens, Brett; Roy, Dominique; Kotsireas, Ilias; Ganesh, Vijay: A nonexistence certificate for projective planes of order ten with weight 15 codewords (2020)

1 2 3 ... 6 7 8 next