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)- 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
- pySecDec: a toolbox for the numerical evaluation of multi-scale integrals
- Minimal extending sets in tournaments
- Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
- Detecting almost symmetries of graphs
- Isomorphism and invariants of parallelisms of projective spaces
- Mappings of Butson-type Hadamard matrices
- Improved bounds for hypo-Hamiltonian graphs
- The Classification of Subfactors with Index at Most 5\frac{1}4
- The Schläfli Fan
- On Ryser's conjecture for linear intersecting multipartite hypergraphs
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- Polynomial reconstruction of signed graphs whose least eigenvalue is close to \(-2\)
- Switching in one-factorisations of complete graphs
- Combinatorial reductions for the Stanley depth of \(I\) and \(S/I\)
- The algebraic matroid of the finite unit norm tight frame (funtf) variety
- Constructions and bounds for mixed-dimension subspace codes
- Further results on the classification of MDS codes
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- Orbital independence in symmetric mathematical programs
- Algebraic polytopes in Normaliz
- Generalized Ramsey numbers through adiabatic quantum optimization
- Obstructions to convexity in neural codes
- Enumerating partial Latin rectangles
- Optimal-depth sorting networks
- On maximal relative projection constants
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Enumerating Steiner triple systems
- Eternal domination and clique covering
- Six variations on a theme: almost planar graphs
- Logic Programming with Graph Automorphism: Integratingnautywith Prolog (Tool Description)
- Borderenergetic Graphs of Order 12
- Steiner triple systems of order 21 with a transversal subdesign \(\mathrm{TD}(3, 6)\)
- Binomial edge ideals of bipartite graphs
- House of graphs 2.0: a database of interesting graphs and more
- Regular graphs of degree at most four that allow two distinct eigenvalues
- Algorithms for finding generalized minimum aberration designs
- On hypercube packings, blocking sets and a covering problem
- 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
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)
