Practical graph isomorphism. II.

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

• McKay's canonical graph labeling algorithm
• Attacks on hard instances of graph isomorphism
• scientific article; zbMATH DE number 1004939
• Benchmark Graphs for Practical Graph Isomorphism
• Efficient isomorphism of Miyazaki graphs

zbMATH Keywords

graph isomorphismpartition refinementtracesnautycanonical labelling

Mathematics Subject Classification ID

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)

• A method for enumerating pairwise compatibility graphs with a given number of vertices
• A new partial geometry \(\mathrm{pg}(5,5,2)\)
• A Note on Universal Point Sets for Planar Graphs
• The sextuply shortened binary Golay code is optimal
• Comparing Wiener complexity with eccentric complexity
• 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
• \(k\)-majority digraphs and the hardness of voting with a constant number of voters
• Computation of new diagonal graph Ramsey numbers
• On a family of highly regular graphs by Brouwer, Ivanov, and Klin
• A proof system for graph (non)-isomorphism verification
• Tight lower and upper bounds for the complexity of canonical colour refinement
• The QAP-polytope and the graph isomorphism problem
• Reconstruction of small graphs and digraphs
• The 4-GDDs of type \(3^56^2\)
• The extended 1-perfect trades in small hypercubes
• Quantum and non-signalling graph isomorphisms
• On the volumes and affine types of trades
• Non-embeddable quasi-residual quasi-symmetric designs
• Bipartite biregular Moore graphs
• The resistance perturbation distance: a metric for the analysis of dynamic networks
• Generating modular lattices of up to 30 elements
• Constructing unlabelled lattices
• Oriented chromatic number of Cartesian products and strong products of paths
• Counting Markov equivalence classes for DAG models on trees
• New refiners for permutation group search
• Enumeration of finite inverse semigroups
• The uniqueness of a distance-regular graph with intersection array \(\{32,27,8,1;1,4,27,32\}\) and related results
• Computing subfields of number fields and applications to Galois group computations
• Nonexistence Certificates for Ovals in a Projective Plane of Order Ten
• A note on universal point sets for planar graphs
• There is no (75,32,10,16) strongly regular graph
• The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
• 16,051 formulas for Ottaviani's invariant of cubic threefolds
• Plurigraph coloring and scheduling problems
• Affine symmetries of orbit polytopes
• Variable symmetry breaking in numerical constraint problems
• On highly regular strongly regular graphs
• Almost equitable partitions and new necessary conditions for network controllability
• Multi-objective optimization model and evolutional solution of network node matching problem
• Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
• Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
• Generating symmetric graphs
• Spectral theory of the non-backtracking Laplacian for graphs
• Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
• Integer sequence discovery from small graphs
• On the seven non-isomorphic solutions of the fifteen schoolgirl problem
• Counting arcs in projective planes via Glynn's algorithm
• Generalized permanental polynomials of graphs
• On the bivariate permanent polynomials of graphs
• Enumerating neighborly polytopes and oriented matroids
• Network Analysis
• Enumeration of Seidel matrices
• There is no McLaughlin geometry
• Regularity and planarity of token graphs
• Perturbations in a signed graph and its index
• On the dichromatic number of surfaces
• Turán numbers for odd wheels
• Partial linear spaces with a rank 3 affine primitive group of automorphisms
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Minimal and canonical images
• On the \(A_{\alpha}\)-characteristic polynomial of a graph
• Independence equivalence classes of paths and cycles
• Transitive tournament tilings in oriented graphs with large minimum total degree
• Graph similarity and approximate isomorphism
• 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

Uses Software

• nauty
• Saucy
• bliss
• geng
• conauto

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)