Practical graph isomorphism. II.
From MaRDI portal
Publication:2437295
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5485559 (Why is no real title available?)
- scientific article; zbMATH DE number 3823850 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3619943 (Why is no real title available?)
- scientific article; zbMATH DE number 3633736 (Why is no real title available?)
- scientific article; zbMATH DE number 3445295 (Why is no real title available?)
- scientific article; zbMATH DE number 1849958 (Why is no real title available?)
- scientific article; zbMATH DE number 898423 (Why is no real title available?)
- A general backtrack algorithm for the isomorphism problem of combinatorial objects
- Algorithms for a class of infinite permutation groups.
- An Efficient Algorithm for Graph Isomorphism
- Conflict propagation and component recursion for canonical labeling
- Engineering an efficient canonical labeling tool for large and sparse graphs
- Errors in graph embedding algorithms
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
- 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
- The graph isomorphism disease
Cited in
(only showing first 100 items - show all)- Network Analysis
- Computation of new diagonal graph Ramsey numbers
- Enumeration of finite inverse semigroups
- Transitive tournament tilings in oriented graphs with large minimum total degree
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- Graph similarity and approximate isomorphism
- On a family of highly regular graphs by Brouwer, Ivanov, and Klin
- Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs
- A note on universal point sets for planar graphs
- On the bivariate permanent polynomials of graphs
- The extended 1-perfect trades in small hypercubes
- Characterization and classification of optimal LCD codes
- Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four
- The minimum number of minimal codewords in an \([n, k]\)-code and in graphic codes
- A proof system for graph (non)-isomorphism verification
- The QAP-polytope and the graph isomorphism problem
- Oriented chromatic number of Cartesian products and strong products of paths
- Complex spherical codes with three inner products
- Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
- The largest pure partial planes of order 6 have size 25
- Integer sequence discovery from small graphs
- Enumeration of Seidel matrices
- There is no McLaughlin geometry
- Affine symmetries of orbit polytopes
- Variable symmetry breaking in numerical constraint problems
- On the seven non-isomorphic solutions of the fifteen schoolgirl problem
- Plurigraph coloring and scheduling problems
- The sextuply shortened binary Golay code is optimal
- Quantum and non-signalling graph isomorphisms
- Non-embeddable quasi-residual quasi-symmetric designs
- Computing subfields of number fields and applications to Galois group computations
- A method for enumerating pairwise compatibility graphs with a given number of vertices
- Reconstruction of small graphs and digraphs
- There is no (75,32,10,16) strongly regular graph
- Generating modular lattices of up to 30 elements
- 16,051 formulas for Ottaviani's invariant of cubic threefolds
- Constructing unlabelled lattices
- \(k\)-majority digraphs and the hardness of voting with a constant number of voters
- Counting arcs in projective planes via Glynn's algorithm
- On highly regular strongly regular graphs
- Regularity and planarity of token graphs
- Multi-objective optimization model and evolutional solution of network node matching problem
- New refiners for permutation group search
- Partial linear spaces with a rank 3 affine primitive group of automorphisms
- Bipartite biregular Moore graphs
- Minimal and canonical images
- Generalized permanental polynomials of graphs
- Perturbations in a signed graph and its index
- The uniqueness of a distance-regular graph with intersection array \(\{32,27,8,1;1,4,27,32\}\) and related results
- On the dichromatic number of surfaces
- The 4-GDDs of type \(3^56^2\)
- On the volumes and affine types of trades
- Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
- Enumerating neighborly polytopes and oriented matroids
- Almost equitable partitions and new necessary conditions for network controllability
- A new partial geometry \(\mathrm{pg}(5,5,2)\)
- On the \(A_{\alpha}\)-characteristic polynomial of a graph
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Independence equivalence classes of paths and cycles
- Generating symmetric graphs
- Nonexistence Certificates for Ovals in a Projective Plane of Order Ten
- Counting Markov equivalence classes for DAG models on trees
- Spectral theory of the non-backtracking Laplacian for graphs
- A Note on Universal Point Sets for Planar Graphs
- Turán numbers for odd wheels
- Tight lower and upper bounds for the complexity of canonical colour refinement
- nauty in Macaulay2
- Improved static symmetry breaking for SAT
- On panel-regular \(\tilde{A}_2\) lattices
- Classification of Graeco-Latin Cubes
- Integer programming for classifying orthogonal arrays
- Small \(f\)-vectors of 3-spheres and of 4-polytopes
- Lower bounds for locally highly connected graphs
- An enumeration of certain projective ternary two-weight codes
- Comparing Wiener complexity with eccentric complexity
- Exploiting symmetries in mathematical programming via orbital independence
- Isotropic matroids. III: Connectivity
- Polytope volume in Normaliz
- 4-cop-win graphs have at least 19 vertices
- Handling symmetries in mixed-integer semidefinite programs
- Kirkman triple systems with subsystems
- A nonexistence certificate for projective planes of order ten with weight 15 codewords
- Biregular graphs with three eigenvalues
- DiscreteZOO: a fingerprint database of discrete objects
- McKay's canonical graph labeling algorithm
- Binary determinantal complexity
- Conics in sextic \(K3\)-surfaces in \(\mathbb{P}^4\)
- Distinguishing graphs with zeta functions and generalized spectra
- An adaptive prefix-assignment technique for symmetry reduction
- On the number of frequency hypercubes \(F^n(4;2,2) \)
- Short certificates for chromatic equivalence
- Quasi-symmetric designs on 56 points
- \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions
- Obstructions for three-coloring graphs without induced paths on six vertices
- Network alignment by discrete Ollivier-Ricci flow
- Enumeration of MOLS of small order
- Uniqueness of codes using semidefinite programming
- New quasi-symmetric designs by the Kramer-Mesner method
- On the minimum weights of binary linear complementary dual codes
- On L-shaped point set embeddings of trees: first non-embeddable examples
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)
