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)- Steiner triple systems of order 21 with a transversal subdesign \(\mathrm{TD}(3, 6)\)
- On the number of frequency hypercubes F^n(4;2,2)
- Quasi-symmetric designs on 56 points
- On the enumeration of minimal non-pairwise compatibility graphs
- On the enumeration of minimal non-pairwise compatibility graphs
- The minimality of the Georges-Kelmans graph
- Cops and robbers on \(2K_2\)-free graphs
- On the Number of Synchronizing Colorings of Digraphs
- A method for enumerating pairwise compatibility graphs with a given number of vertices
- Attacks on hard instances of graph isomorphism
- Computing Autotopism Groups of Partial Latin Rectangles
- A new partial geometry \(\mathrm{pg}(5,5,2)\)
- Classical symmetries and the quantum approximate optimization algorithm
- Combinatorial reductions for the Stanley depth of I and S/I
- nauty in Macaulay2
- Symmetry reduction to optimize a graph-based polynomial from queueing theory
- The sextuply shortened binary Golay code is optimal
- DiscreteZOO: a fingerprint database of discrete objects
- Permutation group algorithms based on directed graphs
- A Note on Universal Point Sets for Planar Graphs
- McKay's canonical graph labeling algorithm
- Complete minors in complements of nonseparating planar graphs
- Comparing Wiener complexity with eccentric complexity
- Polytope volume in Normaliz
- Exploiting symmetries in mathematical programming via orbital independence
- Characterization and classification of optimal LCD codes
- Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
- Iterative equitable partition of graph as a model of constant structure discrete time closed semantic system
- Calculating the symmetry number of flexible sphere clusters
- Complex spherical codes with three inner products
- The largest pure partial planes of order 6 have size 25
- The 4-way intersection problem for kite systems
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- Minimal extending sets in tournaments
- Radius \(r\) extremal graphs of girth 5
- Relating centralities in graphs and the principal eigenvector of its distance matrix
- On the minimum leaf number of cubic graphs
- On a family of highly regular graphs by Brouwer, Ivanov, and Klin
- Novel techniques to speed up the computation of the automorphism group of a graph
- Distinguishing graphs with zeta functions and generalized spectra
- Generalizing cographs to 2-cographs
- Computation of new diagonal graph Ramsey numbers
- Enumerating Steiner triple systems
- Comparison of Atom Maps
- The optimal packing of eight points in the real projective plane
- The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- A proof system for graph (non)-isomorphism verification
- Short certificates for chromatic equivalence
- Conflict vs causality in event structures
- On decomposability of simple cyclic triple systems
- Tight lower and upper bounds for the complexity of canonical colour refinement
- scientific article; zbMATH DE number 7561610 (Why is no real title available?)
- Statistics of Feynman amplitudes in \(\phi^4\)-theory
- Enumeration of Latin squares with conjugate symmetry
- The QAP-polytope and the graph isomorphism problem
- Conflict vs causality in event structures
- pySecDec: a toolbox for the numerical evaluation of multi-scale integrals
- Trinajstić index
- Generalized spectral characterization of mixed graphs
- Error thresholds for arbitrary Pauli noise
- The chromatic number of the square of the 8-cube
- The 4-GDDs of type \(3^56^2\)
- Reconstruction of small graphs and digraphs
- On the (signless) Laplacian permanental polynomials of graphs
- Multiple zeta values in deformation quantization
- The extended 1-perfect trades in small hypercubes
- Canonization of a random circulant graph by counting walks
- Enumerating combinatorial resultant trees
- The Schläfli Fan
- Star-critical Ramsey numbers for cycles versus \(K_4\)
- Biangular lines revisited
- Quantum and non-signalling graph isomorphisms
- Quasi-symmetric \(2\)-\((28,12,11)\) designs with an automorphism of order \(5\)
- Steiner triple systems of order 21 with subsystems
- Detection of common subtrees with identical label distribution
- Maximum independent sets and supervised learning
- On the volumes and affine types of trades
- Biregular graphs with three eigenvalues
- Binary determinantal complexity
- The hidden symmetry of Kontsevich's graph flows on the spaces of Nambu-determinant Poisson brackets
- Construction of all nonisomorphic minimal vertex extensions of the graph by the method of canonical representatives
- Non-embeddable quasi-residual quasi-symmetric designs
- Construction of all minimal edge extensions of the graph with isomorphism rejection
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Bipartite biregular Moore graphs
- Maximum modulus of independence roots of graphs and trees
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- Discrete and metric divisorial gonality can be different
- Automorphism groups and normal forms in Normaliz
- Group theory on quantum Boltzmann machine
- The cone of quasi-semimetrics and exponent matrices of tiled orders
- Algorithms for efficiently computing structural anonymity in complex networks
- Some excluded minors for the spindle surface
- A survey on orbit polynomials
- Improved static symmetry breaking for SAT
- Generating modular lattices of up to 30 elements
- Constructing unlabelled lattices
- Order nine MMIK graphs
- \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions
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)
