Practical graph isomorphism. II.
From MaRDI portal
Publication:2437295
DOI10.1016/J.JSC.2013.09.003zbMATH Open1394.05079DBLPjournals/jsc/McKayP14arXiv1301.1493OpenAlexW1990600049WikidataQ99301767 ScholiaQ99301767MaRDI QIDQ2437295FDOQ2437295
Authors: Adolfo Piperno, Brendan D. McKay 
Publication date: 3 March 2014
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1301.1493
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Cites Work
- Algorithms for a class of infinite permutation groups.
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- The graph isomorphism disease
- Title not available (Why is that?)
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Errors in graph embedding algorithms
- An Efficient Algorithm for Graph Isomorphism
- Title not available (Why is that?)
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A general backtrack algorithm for the isomorphism problem of combinatorial objects
- Title not available (Why is that?)
- Conflict propagation and component recursion for canonical labeling
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- Computing Autotopism Groups of Partial Latin Rectangles
- On the Number of Synchronizing Colorings of Digraphs
- Cops and robbers on \(2K_2\)-free graphs
- Symmetry reduction to optimize a graph-based polynomial from queueing theory
- Classical symmetries and the quantum approximate optimization algorithm
- Complex spherical codes with three inner products
- The largest pure partial planes of order 6 have size 25
- On the minimum leaf number of cubic graphs
- Novel techniques to speed up the computation of the automorphism group of a graph
- On decomposability of simple cyclic triple systems
- Generalizing cographs to 2-cographs
- Title not available (Why is that?)
- Conflict vs causality in event structures
- Generalized spectral characterization of mixed graphs
- On the (signless) Laplacian permanental polynomials of graphs
- Multiple zeta values in deformation quantization
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Maximum modulus of independence roots of graphs and trees
- Discrete and metric divisorial gonality can be different
- Automorphism groups and normal forms in Normaliz
- Constraints for symmetry breaking in graph representation
- Refining invariants for computing autotopism groups of partial Latin rectangles
- Graphs with few Hamiltonian cycles
- Probabilistic symmetries and invariant neural networks
- On digraphs with polygonal restricted numerical range
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- Quaternary complex Hadamard matrices of order 18
- 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 tail dependence matrices. The realization problem for parametric families
- Graphs identified by logics with counting
- Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
- On the classification of quaternary optimal Hermitian LCD codes
- On singular signed graphs with nullspace spanned by a full vector: signed nut graphs
- Strongly regular configurations
- Switching for small strongly regular graphs
- Disjoint direct product decompositions of permutation groups
- Inheritance of oscillation in chemical reaction networks
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- General linear group action on tensors: a candidate for post-quantum cryptography
- On the independence number of $(3, 3)$-Ramsey graphs and the Folkman number $F_e(3, 3; 4)$
- Recursive computation of Feynman periods
- Generating irreducible copositive matrices using the stable set problem
- New bounds for Ramsey numbers \(R ( K_k - e , K_l - e )\)
- Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44
- A census of small transitive groups and vertex-transitive graphs
- Title not available (Why is that?)
- 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
- Equimatchable regular graphs
- Minimum spanning tree cycle intersection problem
- Benchmark Graphs for Practical Graph Isomorphism
- Structural and computational results on platypus graphs
- Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian
- Tritangents to smooth sextic curves
- Vertex removal in biclique graphs
- Collapsibility and homological properties of \(\mathfrak{I}\)-contractible transformations
- The minimality of the Georges-Kelmans graph
- On the number of frequency hypercubes \(F^n(4;2,2) \)
- Quasi-symmetric designs on 56 points
- Combinatorial reductions for the Stanley depth of \(I\) and \(S/I\)
- nauty in Macaulay2
- Polytope volume in Normaliz
- DiscreteZOO: a fingerprint database of discrete objects
- McKay's canonical graph labeling algorithm
- Permutation group algorithms based on directed graphs
- Minimal extending sets in tournaments
- Enumerating Steiner triple systems
- Distinguishing graphs with zeta functions and generalized spectra
- Short certificates for chromatic equivalence
- pySecDec: a toolbox for the numerical evaluation of multi-scale integrals
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- The Schläfli Fan
- Biregular graphs with three eigenvalues
- Binary determinantal complexity
- Improved static symmetry breaking for SAT
- \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions
- Orbital independence in symmetric mathematical programs
- Integer programming for classifying orthogonal arrays
- Small \(f\)-vectors of 3-spheres and of 4-polytopes
- Conics in sextic \(K3\)-surfaces in \(\mathbb{P}^4\)
- Isomorphism and invariants of parallelisms of projective spaces
- Mappings of Butson-type Hadamard matrices
- On Ryser's conjecture for linear intersecting multipartite hypergraphs
- The algebraic matroid of the finite unit norm tight frame (funtf) variety
- Switching in one-factorisations of complete graphs
- On the minimum weights of binary linear complementary dual codes
- Title not available (Why is that?)
- Enumerating partial Latin rectangles
- Obstructions for three-coloring graphs without induced paths on six vertices
- Algorithms for finding generalized minimum aberration designs
- New quasi-symmetric designs by the Kramer-Mesner method
- Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays
- Algebraic polytopes in Normaliz
- Polynomial reconstruction of signed graphs whose least eigenvalue is close to \(-2\)
- Logic Programming with Graph Automorphism: Integratingnautywith Prolog (Tool Description)
- Generating all finite modular lattices of a given size
- On the resistance diameters of graphs and their line graphs
Uses Software
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)
