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
- Classical symmetries and the quantum approximate optimization algorithm
- 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
- 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
- Equimatchable Regular Graphs
- Switching for Small Strongly Regular Graphs
- Constraints for symmetry breaking in graph representation
- Refining invariants for computing autotopism groups of partial Latin rectangles
- 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
- 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
- Disjoint direct product decompositions of permutation groups
- Inheritance of oscillation in chemical reaction networks
- The minimality of the Georges–Kelmans graph
- 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
- Graphs Identified by Logics with Counting
- Title not available (Why is that?)
- Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory
- 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
- Title not available (Why is that?)
- Vertex removal in biclique graphs
- Graphs with few hamiltonian cycles
- Collapsibility and homological properties of \(\mathfrak{I}\)-contractible transformations
- Radius \(r\) extremal graphs of girth 5
- Statistics of Feynman amplitudes in \(\phi^4\)-theory
- Enumeration of Latin squares with conjugate symmetry
- Canonization of a random circulant graph by counting walks
- Enumerating combinatorial resultant trees
- 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
- The hidden symmetry of Kontsevich's graph flows on the spaces of Nambu-determinant Poisson brackets
- Algorithms for efficiently computing structural anonymity in complex networks
- Some excluded minors for the spindle surface
- A survey on orbit polynomials
- Title not available (Why is that?)
- Minimal regular graphs with every edge in a triangle
- Few Hamiltonian cycles in graphs with one or two vertex degrees
- Are hitting formulas hard for resolution?
- On mixed cages
- Edge crossings in random linear arrangements
- Realizable cycle structures in digraphs
- A walk-regular graph, cospectral to its complement, need not be strongly regular
- On regular triangle-distinct graphs
- Polynomial-delay generation of functional digraphs up to isomorphism
- Isomorphism Test for Digraphs with Weighted Edges.
- Breaking symmetries with high dimensional graph invariants and their combination
- On the connectivity and the diameter of betweenness-uniform graphs
- Title not available (Why is that?)
- Graphs isomorphisms under edge-replacements and the family of amoebas
- Wheels: a new criterion for non-convexity of neural codes
- SAT modulo symmetries for graph generation and enumeration
- Mutually orthogonal binary frequency squares of mixed type
- On the classification of skew Hadamard matrices of order 36 and related structures
- Classification of minimal blocking sets in PG(2,9)
- Cographs and 1-sums
- Ordering trees by \(\alpha\)-index
- Colouring problems for symmetric configurations with block size 3
- COMPARISON OF SUFFICIENT DEGREE BASED CONDITIONS FOR HAMILTONIAN GRAPH
- Cohen-Macaulay binomial edge ideals of small graphs
- On 2-factorizations of the complete 3-uniform hypergraph of order 12 minus a 1-factor
- Sparse Steiner triple systems of order 21
- Group divisible designs with block size 4 and group sizes 2 and 5
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)
