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

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

1 2 3 4 5 6 next

  1. Araya, Makoto; Harada, Masaaki: On the minimum weights of binary linear complementary dual codes (2020)
  2. Bernstein, Daniel Irving; Farnsworth, Cameron; Rodriguez, Jose Israel: The algebraic matroid of the finite unit norm tight frame (funtf) variety (2020)
  3. Brown, Jason I.; Cameron, Ben: Maximum modulus of independence roots of graphs and trees (2020)
  4. Chudnovsky, Maria; Goedgebeur, Jan; Schaudt, Oliver; Zhong, Mingxian: Obstructions for three-coloring graphs without induced paths on six vertices (2020)
  5. 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)
  6. Erskine, Grahame; Griggs, Terry; Širáň, Jozef: On the upper embedding of symmetric configurations with block size 3 (2020)
  7. Gebhardt, Volker; Tawn, Stephen: Constructing unlabelled lattices (2020)
  8. Ghorbani, Ebrahim; Kamali, Sara; Khosrovshahi, Gholamreza B.; Krotov, Denis: On the volumes and affine types of trades (2020)
  9. Goedgebeur, Jan; Meersman, Barbara; Zamfirescu, Carol T.: Graphs with few Hamiltonian cycles (2020)
  10. Junttila, Tommi; Karppa, Matti; Kaski, Petteri; Kohonen, Jukka: An adaptive prefix-assignment technique for symmetry reduction (2020)
  11. Krotov, Denis S.: On the OA(1536,13,2,7) and related orthogonal arrays (2020)
  12. Krotov, Denis S.; Vorob’ev, Konstantin V.: On unbalanced Boolean functions with best correlation immunity (2020)
  13. Abrosimov, Mikhaĭl Borisovich; Kamil, Ikhab AAbdzhuldzhabbar Kamil; Lobov, Aleksandr Andreevich: Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives (2019)
  14. Akgün, Özgür; Gent, Ian; Kitaev, Sergey; Zantema, Hans: Solving computational problems in the theory of word-representable graphs (2019)
  15. Atserias, Albert; Mančinska, Laura; Roberson, David E.; Šámal, Robert; Severini, Simone; Varvitsiotis, Antonios: Quantum and non-signalling graph isomorphisms (2019)
  16. Bachmeier, Georg; Brandt, Felix; Geist, Christian; Harrenstein, Paul; Kardel, Keyvan; Peters, Dominik; Seedig, Hans Georg: (k)-majority digraphs and the hardness of voting with a constant number of voters (2019)
  17. Beaton, Iain; Brown, Jason I.; Cameron, Ben: Independence equivalence classes of paths and cycles (2019)
  18. Bohn, Adam; Faenza, Yuri; Fiorini, Samuel; Fisikopoulos, Vissarion; Macchia, Marco; Pashkovich, Kanstantsin: Enumeration of 2-level polytopes (2019)
  19. Brandt, Madeline; Dickinson, William; Ellsworth, AnnaVictoria; Kenkel, Jennifer; Smith, Hanson: Optimal packings of two to four equal circles on any flat torus (2019)
  20. Brouwer, Andries E.; Polak, Sven C.: Uniqueness of codes using semidefinite programming (2019)

1 2 3 4 5 6 next