Practical graph isomorphism, II
2013/01/08 by McKay, Brendan D., Piperno, Adolfo · 50 citations
#05C85 #20B40 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1301.1493
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.
Cited by
- Balance Constants, Majority Cycles, and the Gold Partition Conjecture through Fourteen Elements
- The Uhlenbeck-Ford model in two dimensions: Reference system for fluid-phase free-energy calculations
- Symmetry of Spin Systems as Automorphisms of Undirected Weighted Graphs: Realizability Criterion and Complete Taxonomy up to 14 Spins
- The Excluded Vertex-Minors and Pivot-Minors for Rank-Width at Most Two
- On the Genus Polynomial of Cubic Graphs
- A minimally nonperfectly divisible graph with a bisimplicial vertex
- Two-level D- and A-optimal designs of Ehlich type with run sizes three more than a multiple of four
- Graph Isomorphism: Mixed-Integer Convex Optimization from First-Order Methods
- On the transmission irregular trees with the maximum Wiener index
- Classification of borderenergetic chemical graphs and borderenergetic graphs of order 12
- Mixed birth-death and death-birth updating in structured populations
- Resolvable Triple Arrays
- On the Number of Posets
- A census of Cayley graphs
- Computing Treedepth Obstructions
- Efficient Identification of Permutation Symmetries in Many-Body Hamiltonians via Graph Theory
- A Framework for Handling and Exploiting Symmetry in Benders' Decomposition
- On the order-diameter ratio of girth-diameter cages
- The SCIP Optimization Suite 10.0
- Magnetostriction in the J-K-Γ model: Application of the numerical linked cluster expansion
- A Note on Large Degenerate Induced Subgraphs in Sparse Graphs
- SeQuant Framework for Symbolic and Numerical Tensor Algebra. I. Core Capabilities
- A Systematic Study of Single-Anchor Logical Gadgets
- Steiner systems S(2,6,226) and S(2,6,441) exist
- The Cloven Traveling Salesman: Cycle Covers and the Integrality Gap of Small ATSP Instances
- Equivalence of complex Hadamard matrices
- Enumeration of Tree-like Multigraphs with a Given Number of Vertices, Self-loops and Multiple Edges
- A Classification of Long-Refinement Graphs for Colour Refinement
- Three-dimensional symmetric designs of propriety 3
- Universally Invariant Learning in Equivariant GNNs
- Engineering Dominating Patterns: A Fine-grained Case Study
- A Faster Randomized Algorithm for Vertex Cover: An Automated Approach
- Graph2Region: Efficient Graph Similarity Learning with Structure and Scale Restoration
- On the maximal spread of symmetric Bohemian matrices
- Progress in the study of the (non)existence of genuinely unextendible product bases
- IMProofBench: Benchmarking AI on Research-Level Mathematical Proof Generation
- Marvelous slices of orthogonal matrices
- Steiner 3-designs as extensions
- Enumeration of Laplacian integral and -1,0,1-diagonalizable graphs
- Computations in equivariant Gromov-Witten theory of GKM spaces
- Computational Exploration of Finite Semigroupoids
- The lattice packing problem in dimension 9 by Voronoi's algorithm
- Computer-assisted graph theory: a survey
- IP Models for Minimum Zero Forcing Sets, Forts, and Related Graph Parameters
- Improved lower bounds on the maximum size of graphs with girth 5
- A Hidden Permutation Symmetry of Squared Amplitudes in ABJM Theory
- Anomalous dimensions and critical exponents for the Gross-Neveu-Yukawa model at five loops
- Tropical elliptic curves in 3-space
- Open, Reproducible Calculation of Assembly Indices
- The Cycle Counts of Graphs
Related