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)
- 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
- Constructions and bounds for mixed-dimension subspace codes
- Further results on the classification of MDS codes
- 4-cop-win graphs have at least 19 vertices
- Traces
- Generalized Ramsey numbers through adiabatic quantum optimization
- On maximal relative projection constants
- Classification of Graeco-Latin Cubes
- A Generic Framework for Engineering Graph Canonization Algorithms
- On hypercube packings, blocking sets and a covering problem
- Optimal-depth sorting networks
- Binomial edge ideals of bipartite graphs
- Lower bounds for locally highly connected graphs
- On linear algebraic algorithms for the subgraph matching problem and its variants
- Kirkman triple systems with subsystems
- A nonexistence certificate for projective planes of order ten with weight 15 codewords
- Eternal domination and clique covering
- Borderenergetic Graphs of Order 12
- Regular graphs of degree at most four that allow two distinct eigenvalues
- An adaptive prefix-assignment technique for symmetry reduction
- The Classification of Subfactors with Index at Most 5\frac{1}4
- Obstructions to convexity in neural codes
- On L-shaped point set embeddings of trees: first non-embeddable examples
- Six variations on a theme: almost planar graphs
- Enumeration of MOLS of small order
- Detecting almost symmetries of graphs
- On panel-regular \(\tilde{A}_2\) lattices
- Handling symmetries in mixed-integer semidefinite programs
- Network alignment by discrete Ollivier-Ricci flow
- Enumeration of 2-level polytopes
- \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions
- An enumeration of certain projective ternary two-weight codes
- Improved bounds for hypo-Hamiltonian graphs
- House of graphs 2.0: a database of interesting graphs and more
- Isotropic matroids. III: Connectivity
- Uniqueness of codes using semidefinite programming
- On the enumeration of minimal non-pairwise compatibility graphs
- On the enumeration of minimal non-pairwise compatibility graphs
- Steiner triple systems of order 21 with a transversal subdesign \(\mathrm{TD}(3, 6)\)
- 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
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)
