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; bliss; OEIS; House of Graphs; Cliquer; GitHub; Magma; GENREG; snarkhunter; CPLEX; Mathematica; Macaulay2; GRAPE; libexact; SCIP; BEE; plantri; conauto Cited in: 194 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Practical graph isomorphism. II. Zbl 1394.05079McKay, Brendan D.; Piperno, Adolfo 2014 all top 5 Cited by 434 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 334 more Authors all top 5 Cited 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 all top 5 Cited in 31 Fields 150 Combinatorics (05-XX) 43 Computer science (68-XX) 23 Operations research, mathematical programming (90-XX) 15 Information and communication theory, circuits (94-XX) 12 Group theory and generalizations (20-XX) 10 Convex and discrete geometry (52-XX) 9 Linear and multilinear algebra; matrix theory (15-XX) 9 Geometry (51-XX) 8 Quantum theory (81-XX) 7 Algebraic geometry (14-XX) 5 Order, lattices, ordered algebraic structures (06-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Number theory (11-XX) 4 Statistics (62-XX) 4 Numerical analysis (65-XX) 4 Biology and other natural sciences (92-XX) 3 Commutative algebra (13-XX) 3 Algebraic topology (55-XX) 3 Probability theory and stochastic processes (60-XX) 1 Mathematical logic and foundations (03-XX) 1 Associative rings and algebras (16-XX) 1 Category theory; homological algebra (18-XX) 1 Real functions (26-XX) 1 Ordinary differential equations (34-XX) 1 Dynamical systems and ergodic theory (37-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Functional analysis (46-XX) 1 Differential geometry (53-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Systems theory; control (93-XX) Citations by Year