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
- 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
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)
