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
• 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
• Complex spherical codes with three inner products
• The largest pure partial planes of order 6 have size 25
• \(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
• 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
• Comparing Wiener complexity with eccentric complexity
• 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

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)