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)- Oriented chromatic number of Cartesian products and strong products of paths
- Minimal regular graphs with every edge in a triangle
- Few Hamiltonian cycles in graphs with one or two vertex degrees
- Counting Markov equivalence classes for DAG models on trees
- Efficient Graph Kernels for Textual Entailment Recognition
- Orbital independence in symmetric mathematical programs
- Symmetry breaking constraints for the minimum deficiency problem
- Mappings of Butson-type Hadamard matrices
- Small \(f\)-vectors of 3-spheres and of 4-polytopes
- On Ryser's conjecture for linear intersecting multipartite hypergraphs
- Integer programming for classifying orthogonal arrays
- The algebraic matroid of the finite unit norm tight frame (funtf) variety
- Are hitting formulas hard for resolution?
- Constraints for symmetry breaking in graph representation
- Conics in sextic \(K3\)-surfaces in \(\mathbb{P}^4\)
- Exhaustive search for snake-in-the-box codes
- Isomorphism and invariants of parallelisms of projective spaces
- Computing maximum unavoidable subgraphs using SAT solvers
- Refining invariants for computing autotopism groups of partial Latin rectangles
- The SU(3) spin model with chemical potential by series expansion techniques
- Switching in one-factorisations of complete graphs
- On digraphs with polygonal restricted numerical range
- On trees with algebraic connectivity greater than or equal to \(2(1-\cos(\frac{\pi}{7}))\)
- On stepwise transmission irregular graphs
- On mixed cages
- New refiners for permutation group search
- Graphs with few Hamiltonian cycles
- Probabilistic symmetries and invariant neural networks
- Enumeration of finite inverse semigroups
- Edge crossings in random linear arrangements
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- On the minimum weights of binary linear complementary dual codes
- Realizable cycle structures in digraphs
- A walk-regular graph, cospectral to its complement, need not be strongly regular
- Spectrally robust graph isomorphism
- Enumerating partial Latin rectangles
- Quaternary complex Hadamard matrices of order 18
- scientific article; zbMATH DE number 7008235 (Why is no real title available?)
- 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 regular triangle-distinct graphs
- Obstructions for three-coloring graphs without induced paths on six vertices
- Algorithms for finding generalized minimum aberration designs
- Polynomial-delay generation of functional digraphs up to isomorphism
- New quasi-symmetric designs by the Kramer-Mesner method
- Breaking symmetries with high dimensional graph invariants and their combination
- Constructions of cospectral graphs with different zero forcing numbers
- On the connectivity and the diameter of betweenness-uniform graphs
- Graphs isomorphisms under edge-replacements and the family of amoebas
- Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
- Wheels: a new criterion for non-convexity of neural codes
- The uniqueness of a distance-regular graph with intersection array \(\{32,27,8,1;1,4,27,32\}\) and related results
- Efficient isomorphism of Miyazaki graphs
- SAT modulo symmetries for graph generation and enumeration
- Mutually orthogonal binary frequency squares of mixed type
- Computing subfields of number fields and applications to Galois group computations
- On tail dependence matrices. The realization problem for parametric families
- Algebraic polytopes in Normaliz
- ScrewBox: a randomized certifying graph-non-isomorphism algorithm
- On the classification of skew Hadamard matrices of order 36 and related structures
- Hyperbolic triangular buildings without periodic planes of genus 2
- Graphs identified by logics with counting
- Classification of minimal blocking sets in PG(2,9)
- Cographs and 1-sums
- Ordering trees by \(\alpha\)-index
- Colouring problems for symmetric configurations with block size 3
- Cohen-Macaulay binomial edge ideals of small graphs
- Polynomial reconstruction of signed graphs whose least eigenvalue is close to \(-2\)
- Traces
- A note on universal point sets for planar graphs
- Generating all finite modular lattices of a given size
- On 2-factorizations of the complete 3-uniform hypergraph of order 12 minus a 1-factor
- An exponential lower bound for individualization-refinement algorithms for graph isomorphism
- Logic Programming with Graph Automorphism: Integratingnautywith Prolog (Tool Description)
- Constructions and bounds for mixed-dimension subspace codes
- Further results on the classification of MDS codes
- There is no (75,32,10,16) strongly regular graph
- Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
- Nonexistence Certificates for Ovals in a Projective Plane of Order Ten
- On the classification of quaternary optimal Hermitian LCD codes
- Sparse Steiner triple systems of order 21
- On the resistance diameters of graphs and their line graphs
- The power of the Weisfeiler-Leman algorithm to decompose graphs
- 4-cop-win graphs have at least 19 vertices
- Automorphism groups of some families of bipartite graphs
- Group divisible designs with block size 4 and group sizes 2 and 5
- The maximum number of columns in E(s2) $\,E({s}^{2})$‐optimal supersaturated designs with 16 rows and smax=4 ${s}_{{\rm{\max }}}=4$ is 60
- Intersecting and 2‐intersecting hypergraphs with maximal covering number: The Erdős–Lovász theme revisited
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- The smallest hard trees
- The smallest 5-chromatic tournament
- scientific article; zbMATH DE number 7764126 (Why is no real title available?)
- On singular signed graphs with nullspace spanned by a full vector: signed nut graphs
- Strongly regular configurations
- The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
- 16,051 formulas for Ottaviani's invariant of cubic threefolds
- Generalized Ramsey numbers through adiabatic quantum optimization
- On maximal relative projection constants
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)
