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

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

1 2 3 ... 5 6 7 next

  1. Araya, Makoto; Harada, Masaaki: On the minimum weights of binary linear complementary dual codes (2020)
  2. Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg: On Weisfeiler-Leman invariance: subgraph counts and related graph properties (2020)
  3. Bernstein, Daniel Irving; Farnsworth, Cameron; Rodriguez, Jose Israel: The algebraic matroid of the finite unit norm tight frame (funtf) variety (2020)
  4. Bikov, Aleksandar; Nenov, Nedyalko: On the independence number of ((3,3))-Ramsey graphs and the Folkman number (F_e(3,3;4)) (2020)
  5. 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)
  6. Brown, Jason I.; Cameron, Ben: Maximum modulus of independence roots of graphs and trees (2020)
  7. Chudnovsky, Maria; Goedgebeur, Jan; Schaudt, Oliver; Zhong, Mingxian: Obstructions for three-coloring graphs without induced paths on six vertices (2020)
  8. 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)
  9. Erskine, Grahame; Griggs, Terry; Širáň, Jozef: On the upper embedding of symmetric configurations with block size 3 (2020)
  10. Falcón, Raúl M.; Stones, Rebecca J.: Enumerating partial Latin rectangles (2020)
  11. Gebhardt, Volker; Tawn, Stephen: Constructing unlabelled lattices (2020)
  12. Ghorbani, Ebrahim; Kamali, Sara; Khosrovshahi, Gholamreza B.; Krotov, Denis: On the volumes and affine types of trades (2020)
  13. Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
  14. Gomes, Guilherme de C. M.; Groshaus, Marina; Lima, Carlos V. G. C.; dos Santos, Vinicius F.: Intersection graph of maximal stars (2020)
  15. Guan, Y.; Shi, M. J.; Krotov, D. S.: Steiner triple systems of order 21 with a transversal subdesign (\mathrmTD(3, 6)) (2020)
  16. Hojny, Christopher: Packing, partitioning, and covering symresacks (2020)
  17. Holt, Derek; Royle, Gordon: A census of small transitive groups and vertex-transitive graphs (2020)
  18. Joswig, Michael; Panizzut, Marta; Sturmfels, Bernd: The Schläfli Fan (2020)
  19. Junttila, Tommi; Karppa, Matti; Kaski, Petteri; Kohonen, Jukka: An adaptive prefix-assignment technique for symmetry reduction (2020)
  20. Klocker, Benedikt; Fleischner, Herbert; Raidl, Günther R.: A model for finding transition-minors (2020)

1 2 3 ... 5 6 7 next