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

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

1 2 3 ... 5 6 7 next

  1. Abrosimov, Mikhaĭl Borisovich; Sudani, Hayder Hussein Karim; Lobov, Aleksandr Andreevich: Construction of all minimal edge extensions of the graph with isomorphism rejection (2020)
  2. 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)
  3. Alemany-Puig, Lluís; Ferrer-i-Cancho, Ramon: Edge crossings in random linear arrangements (2020)
  4. Araya, Makoto; Harada, Masaaki: On the minimum weights of binary linear complementary dual codes (2020)
  5. Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg: On Weisfeiler-Leman invariance: subgraph counts and related graph properties (2020)
  6. Banks, Peter; Panzer, Erik; Pym, Brent: Multiple zeta values in deformation quantization (2020)
  7. Berčič, Katja; Vidali, Janoš: DiscreteZOO: a fingerprint database of discrete objects (2020)
  8. Bernstein, Daniel Irving; Farnsworth, Cameron; Rodriguez, Jose Israel: The algebraic matroid of the finite unit norm tight frame (funtf) variety (2020)
  9. 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)
  10. Bikov, Aleksandar; Nenov, Nedyalko: On the independence number of ((3,3))-Ramsey graphs and the Folkman number (F_e(3,3;4)) (2020)
  11. 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)
  12. Brown, Jason I.; Cameron, Ben: Maximum modulus of independence roots of graphs and trees (2020)
  13. Chudnovsky, Maria; Goedgebeur, Jan; Schaudt, Oliver; Zhong, Mingxian: Obstructions for three-coloring graphs without induced paths on six vertices (2020)
  14. Danan, Eiran; Falcón, Raúl M.; Kotlar, Dani; Marbach, Trent G.; Stones, Rebecca J.: Refining invariants for computing autotopism groups of partial Latin rectangles (2020)
  15. Erskine, Grahame; Griggs, Terry; Širáň, Jozef: On the upper embedding of symmetric configurations with block size 3 (2020)
  16. Falcón, Raúl M.; Stones, Rebecca J.: Enumerating partial Latin rectangles (2020)
  17. Gebhardt, Volker; Tawn, Stephen: Constructing unlabelled lattices (2020)
  18. Ghorbani, Ebrahim; Kamali, Sara; Khosrovshahi, Gholamreza B.; Krotov, Denis: On the volumes and affine types of trades (2020)
  19. Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
  20. Gomes, Guilherme de C. M.; Groshaus, Marina; Lima, Carlos V. G. C.; dos Santos, Vinicius F.: Intersection graph of maximal stars (2020)

1 2 3 ... 5 6 7 next