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)- 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
- Generalizing cographs to 2-cographs
- Benchmark Graphs for Practical Graph Isomorphism
- On decomposability of simple cyclic triple systems
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- Recursive computation of Feynman periods
- Symmetry reduction to optimize a graph-based polynomial from queueing theory
- Graphs identified by logics with counting
- Maximum modulus of independence roots of graphs and trees
- The minimality of the Georges-Kelmans graph
- Classification of MDS codes over small alphabets
- Constraints for symmetry breaking in graph representation
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Structural and computational results on platypus graphs
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- On the number of minimal codewords in codes generated by the adjacency matrix of a graph
- The smallest pair of cospectral cubic graphs with different chromatic indexes
- Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- Classical symmetries and the quantum approximate optimization algorithm
- On the minimum leaf number of cubic graphs
- Novel techniques to speed up the computation of the automorphism group of a graph
- Disjoint direct product decompositions of permutation groups
- Conflict vs causality in event structures
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- Vertex removal in biclique graphs
- nauty in Macaulay2
- Improved static symmetry breaking for SAT
- On panel-regular \(\tilde{A}_2\) lattices
- Classification of Graeco-Latin Cubes
- Integer programming for classifying orthogonal arrays
- Small \(f\)-vectors of 3-spheres and of 4-polytopes
- Lower bounds for locally highly connected graphs
- An enumeration of certain projective ternary two-weight codes
- Comparing Wiener complexity with eccentric complexity
- Exploiting symmetries in mathematical programming via orbital independence
- Isotropic matroids. III: Connectivity
- Polytope volume in Normaliz
- 4-cop-win graphs have at least 19 vertices
- Handling symmetries in mixed-integer semidefinite programs
- Kirkman triple systems with subsystems
- A nonexistence certificate for projective planes of order ten with weight 15 codewords
- Biregular graphs with three eigenvalues
- DiscreteZOO: a fingerprint database of discrete objects
- McKay's canonical graph labeling algorithm
- Binary determinantal complexity
- Conics in sextic \(K3\)-surfaces in \(\mathbb{P}^4\)
- Distinguishing graphs with zeta functions and generalized spectra
- An adaptive prefix-assignment technique for symmetry reduction
- On the number of frequency hypercubes \(F^n(4;2,2) \)
- Short certificates for chromatic equivalence
- Quasi-symmetric designs on 56 points
- \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions
- Obstructions for three-coloring graphs without induced paths on six vertices
- Network alignment by discrete Ollivier-Ricci flow
- Enumeration of MOLS of small order
- Uniqueness of codes using semidefinite programming
- New quasi-symmetric designs by the Kramer-Mesner method
- On the minimum weights of binary linear complementary dual codes
- On L-shaped point set embeddings of trees: first non-embeddable examples
- On the enumeration of minimal non-pairwise compatibility graphs
- On the enumeration of minimal non-pairwise compatibility graphs
- Generating all finite modular lattices of a given size
- Permutation group algorithms based on directed graphs
- scientific article; zbMATH DE number 7008235 (Why is no real title available?)
- Traces
- On the resistance diameters of graphs and their line 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)
