Practical graph isomorphism. II.
From MaRDI portal
Publication:2437295
Abstract: We report the current state of the graph isomorphism problem from the practical point of view. After describing the general principles of the refinement-individualization paradigm and proving its validity, we explain how it is implemented in several of the key programs. In particular, we bring the description of the best known program nauty up to date and describe an innovative approach called Traces that outperforms the competitors for many difficult graph classes. Detailed comparisons against saucy, Bliss and conauto are presented.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485559 (Why is no real title available?)
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3619943 (Why is no real title available?)
- scientific article; zbMATH DE number 3633736 (Why is no real title available?)
- scientific article; zbMATH DE number 3445295 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 898423 (Why is no real title available?)
- A general backtrack algorithm for the isomorphism problem of combinatorial objects
- Algorithms for a class of infinite permutation groups.
- An Efficient Algorithm for Graph Isomorphism
- Conflict propagation and component recursion for canonical labeling
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Errors in graph embedding algorithms
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
- The graph isomorphism disease
Cited in
(only showing first 100 items - show all)- Network Analysis
- Computation of new diagonal graph Ramsey numbers
- Enumeration of finite inverse semigroups
- Transitive tournament tilings in oriented graphs with large minimum total degree
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- Graph similarity and approximate isomorphism
- On a family of highly regular graphs by Brouwer, Ivanov, and Klin
- Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
- A note on universal point sets for planar graphs
- On the bivariate permanent polynomials of graphs
- The extended 1-perfect trades in small hypercubes
- Characterization and classification of optimal LCD codes
- Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
- The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
- A proof system for graph (non)-isomorphism verification
- The QAP-polytope and the graph isomorphism problem
- Oriented chromatic number of Cartesian products and strong products of paths
- Complex spherical codes with three inner products
- Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
- The largest pure partial planes of order 6 have size 25
- Integer sequence discovery from small graphs
- Enumeration of Seidel matrices
- There is no McLaughlin geometry
- Affine symmetries of orbit polytopes
- Variable symmetry breaking in numerical constraint problems
- On the seven non-isomorphic solutions of the fifteen schoolgirl problem
- Plurigraph coloring and scheduling problems
- The sextuply shortened binary Golay code is optimal
- Quantum and non-signalling graph isomorphisms
- Non-embeddable quasi-residual quasi-symmetric designs
- Computing subfields of number fields and applications to Galois group computations
- A method for enumerating pairwise compatibility graphs with a given number of vertices
- Reconstruction of small graphs and digraphs
- There is no (75,32,10,16) strongly regular graph
- Generating modular lattices of up to 30 elements
- 16,051 formulas for Ottaviani's invariant of cubic threefolds
- Constructing unlabelled lattices
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- Counting arcs in projective planes via Glynn's algorithm
- On highly regular strongly regular graphs
- Regularity and planarity of token graphs
- Multi-objective optimization model and evolutional solution of network node matching problem
- New refiners for permutation group search
- Partial linear spaces with a rank 3 affine primitive group of automorphisms
- Bipartite biregular Moore graphs
- Minimal and canonical images
- Generalized permanental polynomials of graphs
- Perturbations in a signed graph and its index
- The uniqueness of a distance-regular graph with intersection array \(\{32,27,8,1;1,4,27,32\}\) and related results
- On the dichromatic number of surfaces
- The 4-GDDs of type \(3^56^2\)
- On the volumes and affine types of trades
- Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
- Enumerating neighborly polytopes and oriented matroids
- Almost equitable partitions and new necessary conditions for network controllability
- A new partial geometry \(\mathrm{pg}(5,5,2)\)
- On the \(A_{\alpha}\)-characteristic polynomial of a graph
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Independence equivalence classes of paths and cycles
- Generating symmetric graphs
- Nonexistence Certificates for Ovals in a Projective Plane of Order Ten
- Counting Markov equivalence classes for DAG models on trees
- Spectral theory of the non-backtracking Laplacian for graphs
- A Note on Universal Point Sets for Planar Graphs
- Turán numbers for odd wheels
- Tight lower and upper bounds for the complexity of canonical colour refinement
- Conflict vs causality in event structures
- Generating irreducible copositive matrices using the stable set problem
- General linear group action on tensors: a candidate for post-quantum cryptography
- Discrete and metric divisorial gonality can be different
- New bounds for Ramsey numbers \(R ( K_k - e , K_l - e )\)
- Computing Autotopism Groups of Partial Latin Rectangles
- Automorphism groups and normal forms in Normaliz
- Hadamard diagonalizable graphs of order at most 36
- Cartesian lattice counting by the vertical 2-sum
- Cohen-Macaulay binomial edge ideals and accessible graphs
- Spectral characterizations of tournaments
- On singular signed graphs with nullspace spanned by a full vector: signed nut graphs
- On the Number of Synchronizing Colorings of Digraphs
- Strongly regular configurations
- On the independence number of $(3, 3)$-Ramsey graphs and the Folkman number $F_e(3, 3; 4)$
- On the (signless) Laplacian permanental polynomials of graphs
- Multiple zeta values in deformation quantization
- Inheritance of oscillation in chemical reaction networks
- A census of small transitive groups and vertex-transitive graphs
- Quaternary complex Hadamard matrices of order 18
- Equimatchable regular graphs
- Cops and robbers on \(2K_2\)-free graphs
- Refining invariants for computing autotopism groups of partial Latin rectangles
- Tritangents to smooth sextic curves
- Switching for small strongly regular graphs
- Graphs with few Hamiltonian cycles
- On tail dependence matrices. The realization problem for parametric families
- Probabilistic symmetries and invariant neural networks
- Minimum spanning tree cycle intersection problem
- On digraphs with polygonal restricted numerical range
- Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
- On the classification of quaternary optimal Hermitian LCD codes
- Collapsibility and homological properties of \(\mathfrak{I}\)-contractible transformations
- Generalized spectral characterization of mixed graphs
This page was built for publication: Practical graph isomorphism. II.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437295)
