×

Traces

swMATH ID: 7823
Software Authors: Adolfo Piperno
Description: 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.
Homepage: http://pallini.di.uniroma1.it/
Related Software: nauty; GAP; SageMath; OEIS; House of Graphs; GitHub; Magma; GENREG; snarkhunter; CPLEX; Mathematica; Cliquer; Macaulay2; GRAPE; libexact; SCIP; BEE; plantri; conauto; MINION
Referenced in: 194 Publications

Standard Articles

1 Publication describing the Software, including 1 Publication in zbMATH Year
Practical graph isomorphism. II. Zbl 1394.05079
McKay, Brendan D.; Piperno, Adolfo
2014
all top 5

Referenced by 433 Authors

9 Goedgebeur, Jan
9 Östergård, Patric R. J.
6 Krotov, Denis S.
4 Abrosimov, Mikhail Borisovich
4 Codish, Michael
4 Jefferson, Christopher
4 Liu, Shunyi
4 McKay, Brendan D.
4 Zamfirescu, Carol T.
3 Bulutoglu, Dursun A.
3 Cameron, Ben
3 Krčadinac, Vedran
3 Lobov, Aleksandr Andreevich
3 Pfeiffer, Markus
3 Ryan, Kenneth Joseph
3 Waldecker, Rebecca
3 Wanless, Ian M.
2 Araya, Makoto
2 Bolognini, Davide
2 Brandt, Felix
2 Breen, Jane
2 Brown, Jason Ira
2 Cameron, Thomas R.
2 da Silva, Celso M. jun.
2 Dias, Gustavo Fruet
2 Falcón Ganfornina, Raúl Manuel
2 Grohe, Martin
2 Harada, Masaaki
2 Harrenstein, Paul
2 Hojny, Christopher
2 Ikenmeyer, Christian
2 Kamil, Ikhab AAbdzhuldzhabbar Kamil
2 Kaski, Petteri
2 Kiefer, Sandra
2 Kohonen, Jukka
2 Kokkala, Janne I.
2 Liberti, Leo
2 Macchia, Antonio
2 Neuen, Daniel
2 Pech, Christian
2 Piperno, Adolfo
2 Polak, Sven C.
2 Royle, Gordon F.
2 Schaudt, Oliver
2 Scheucher, Manfred
2 Schweitzer, Pascal
2 Seedig, Hans Georg
2 Shi, Minjia
2 Soicher, Leonard H.
2 Stones, Rebecca J.
2 Strazzanti, Francesco
2 Sudani, Hayder Hussein Karim
2 Szöllősi, Ferenc
2 Turcotte, Jérémie
2 Van Cleemput, Nicolas
2 Villagrán, Ralihe R.
1 Abdesselam, Abdelmalek
1 Abiad, Aida
1 Aboulker, Pierre
1 Abreu, Marién
1 Adamaszek, Anna
1 Adamaszek, Michal
1 Adams, Peter J.
1 Adriaens, Florian
1 Aguilar, Cesar O.
1 Akbari, Saieed
1 Akgün, Özgür
1 Alahmadi, Adel N.
1 Aldred, Robert E. L.
1 Alemany-Puig, Lluís
1 Altinakar, Sivan
1 Araujo-Pardo, Gabriela
1 Arvind, Vikraman
1 Atserias, Albert
1 Aurora, Pawan Kumar
1 Azam, Naveed Ahmed
1 Azarija, Jernej
1 Bach, Eric
1 Bachmeier, Georg
1 Banaji, Murad
1 Banks, Peter
1 Bausch, Johannes
1 Beaton, Iain
1 Berčič, Katja
1 Berkholz, Christoph
1 Bernstein, Daniel Irving
1 Bian, Zhengbing
1 Bikov, Aleksandar
1 Bird, Emily M.
1 Bliss, Nathan
1 Bogaerts, Bart
1 Bohn, Adam
1 Bonsma, Paul S.
1 Botler, Fábio
1 Brandt, Madeline
1 Bright, Curtis
1 Brijder, Robert
1 Brimkov, Boris
1 Brinkmann, Gunnar
1 Brinkmann, Philip
...and 333 more Authors
all top 5

Referenced in 85 Serials

18 Discrete Applied Mathematics
15 Discrete Mathematics
9 The Electronic Journal of Combinatorics
7 Journal of Symbolic Computation
7 The Australasian Journal of Combinatorics
6 Linear Algebra and its Applications
5 Mathematics of Computation
5 Designs, Codes and Cryptography
4 Applied Mathematics and Computation
4 Journal of Algebra
4 European Journal of Combinatorics
4 Graphs and Combinatorics
4 Discussiones Mathematicae. Graph Theory
4 Journal of Graph Algorithms and Applications
3 Journal of Computer and System Sciences
3 Discrete & Computational Geometry
3 Mathematical Programming Computation
3 Prikladnaya Diskretnaya Matematika
2 Information Processing Letters
2 Journal of Combinatorial Theory. Series A
2 Journal of Combinatorial Theory. Series B
2 SIAM Journal on Discrete Mathematics
2 Constraints
2 Data Mining and Knowledge Discovery
2 Ars Mathematica Contemporanea
2 Izvestiya Saratovskogo Universiteta. Novaya Seriya. Seriya Matematika, Mekhanika, Informatika
2 Electronic Journal of Graph Theory and Applications
1 Artificial Intelligence
1 Journal of Mathematical Analysis and Applications
1 Problems of Information Transmission
1 Advances in Mathematics
1 Algebra Universalis
1 Automatica
1 Geometriae Dedicata
1 Indiana University Mathematics Journal
1 Information Sciences
1 Inventiones Mathematicae
1 Journal of Geometry
1 Journal of Graph Theory
1 Journal of Pure and Applied Algebra
1 Nagoya Mathematical Journal
1 Semigroup Forum
1 SIAM Journal on Computing
1 Siberian Mathematical Journal
1 Advances in Applied Mathematics
1 Mathematical Social Sciences
1 Advances in Mathematics
1 Order
1 Journal of Complexity
1 Information and Computation
1 Computers & Operations Research
1 Annals of Operations Research
1 Pattern Recognition
1 Applicable Algebra in Engineering, Communication and Computing
1 Journal of Nonlinear Science
1 Experimental Mathematics
1 Journal of Algebraic Combinatorics
1 Computational and Applied Mathematics
1 The Journal of Artificial Intelligence Research (JAIR)
1 Boletín de la Sociedad Matemática Mexicana. Third Series
1 ELA. The Electronic Journal of Linear Algebra
1 Theory of Computing Systems
1 Journal of Combinatorial Optimization
1 Journal of Integer Sequences
1 Extremes
1 Journal of High Energy Physics
1 Theory and Practice of Logic Programming
1 Journal of Applied Mathematics
1 Journal of Statistical Mechanics: Theory and Experiment
1 Discrete Optimization
1 SIGMA. Symmetry, Integrability and Geometry: Methods and Applications
1 Proyecciones
1 Contributions to Discrete Mathematics
1 Mathematics in Computer Science
1 Journal of Physics A: Mathematical and Theoretical
1 Logical Methods in Computer Science
1 Vestnik Yuzhno-Ural’skogo Gosudarstvennogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie
1 Cryptography and Communications
1 Symmetry
1 Iranian Journal of Mathematical Chemistry
1 Transactions on Combinatorics
1 Research in the Mathematical Sciences
1 Journal of Logical and Algebraic Methods in Programming
1 SIAM Journal on Applied Algebra and Geometry
1 Algebraic Combinatorics

Referencing Publications by Year