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
- 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
- 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?)
- 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)- The Schläfli Fan
- Detecting almost symmetries of graphs
- Oriented chromatic number of Cartesian products and strong products of paths
- The QAP-polytope and the graph isomorphism problem
- Perturbations in a signed graph and its index
- On panel-regular \(\tilde{A}_2\) lattices
- Six variations on a theme: almost planar graphs
- Counting arcs in projective planes via Glynn's algorithm
- Enumeration of Seidel matrices
- There is no McLaughlin geometry
- The resistance perturbation distance: a metric for the analysis of dynamic networks
- Turán numbers for odd wheels
- Network alignment by discrete Ollivier-Ricci flow
- The sextuply shortened binary Golay code is optimal
- On a family of highly regular graphs by Brouwer, Ivanov, and Klin
- Computing subfields of number fields and applications to Galois group computations
- On the \(A_{\alpha}\)-characteristic polynomial of a graph
- Binomial edge ideals of bipartite graphs
- Counting Markov equivalence classes for DAG models on trees
- Minimal and canonical images
- New refiners for permutation group search
- There is no (75,32,10,16) strongly regular graph
- Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree
- Bipartite biregular Moore graphs
- A method for enumerating pairwise compatibility graphs with a given number of vertices
- Traces
- The algebraic matroid of the finite unit norm tight frame (funtf) variety
- Complex spherical codes with three inner products
- The largest pure partial planes of order 6 have size 25
- Conflict vs causality in event structures
- Uniqueness of codes using semidefinite programming
- On the (signless) Laplacian permanental polynomials of graphs
- Multiple zeta values in deformation quantization
- Enumeration of finite inverse semigroups
- The extended 1-perfect trades in small hypercubes
- 4-cop-win graphs have at least 19 vertices
- A new partial geometry \(\mathrm{pg}(5,5,2)\)
- Permutation group algorithms based on directed graphs
- Disjoint direct product decompositions of permutation groups
- New bounds for Ramsey numbers \(R ( K_k - e , K_l - e )\)
- On highly regular strongly regular graphs
- 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
- Tritangents to smooth sextic curves
- Vertex removal in biclique graphs
- Classical symmetries and the quantum approximate optimization algorithm
- House of graphs 2.0: a database of interesting graphs and more
- Generalizing cographs to 2-cographs
- Discrete and metric divisorial gonality can be different
- On the dichromatic number of surfaces
- Automorphism groups and normal forms in Normaliz
- On digraphs with polygonal restricted numerical range
- Hadamard diagonalizable graphs of order at most 36
- Cartesian lattice counting by the vertical 2-sum
- Cohen-Macaulay binomial edge ideals and accessible graphs
- Collapsibility and homological properties of \(\mathfrak{I}\)-contractible transformations
- Spectral characterizations of tournaments
- Multi-objective optimization model and evolutional solution of network node matching problem
- Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
- Non-embeddable quasi-residual quasi-symmetric designs
- 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
- The 4-GDDs of type \(3^56^2\)
- Practical post-quantum signature schemes from isomorphism problems of trilinear forms
- Maximum modulus of independence roots of graphs and trees
- General linear group action on tensors: a candidate for post-quantum cryptography
- On the minimum weights of binary linear complementary dual codes
- Enumerating partial Latin rectangles
- A census of small transitive groups and vertex-transitive graphs
- Steiner triple systems of order 21 with a transversal subdesign \(\mathrm{TD}(3, 6)\)
- On tail dependence matrices. The realization problem for parametric families
- A model for finding transition-minors
- Packing, partitioning, and covering symresacks
- Counting frequent patterns in large labeled graphs: a hypergraph-based approach
- Intersection graph of maximal stars
- Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach
- A note on universal point sets for planar graphs
- DiscreteZOO: a fingerprint database of discrete objects
- Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results
- Generalized spectral characterization of mixed graphs
- Star-critical Ramsey numbers for cycles versus \(K_4\)
- Biangular lines revisited
- Group theory on quantum Boltzmann machine
- Cops and robbers on \(2K_2\)-free graphs
- The cone of quasi-semimetrics and exponent matrices of tiled orders
- On the resistance diameters of graphs and their line graphs
- On trees with algebraic connectivity greater than or equal to \(2(1-\cos(\frac{\pi}{7}))\)
- Mixed-integer programming techniques for the connected max-\(k\)-cut problem
- On stepwise transmission irregular graphs
- Inheritance of oscillation in chemical reaction networks
- Generating modular lattices of up to 30 elements
- On the \(\mathrm{OA}(1536,13,2,7)\) and related orthogonal arrays
- Constructing unlabelled lattices
- Obstructions for three-coloring graphs without induced paths on six vertices
- On the volumes and affine types of trades
- On the upper embedding of symmetric configurations with block size 3
- Refining invariants for computing autotopism groups of partial Latin rectangles
- On unbalanced Boolean functions with best correlation immunity
- Generalized permanental polynomials of graphs
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)
