Practical graph isomorphism. II.

DOI10.1016/j.jsc.2013.09.003zbMath1394.05079arXiv1301.1493OpenAlexW1990600049WikidataQ99301767 ScholiaQ99301767MaRDI QIDQ2437295

Adolfo Piperno, Brendan D. McKay

Publication date: 3 March 2014

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.1493

zbMATH Keywords

tracesgraph isomorphismpartition refinementnautycanonical labelling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (only showing first 100 items - show all)

Discrete and metric divisorial gonality can be different ⋮ On the number of frequency hypercubes \(F^n(4;2,2) \) ⋮ On the dichromatic number of surfaces ⋮ Automorphism groups and normal forms in Normaliz ⋮ Quasi-symmetric designs on 56 points ⋮ Comparing Wiener complexity with eccentric complexity ⋮ Detecting almost symmetries of graphs ⋮ Biregular graphs with three eigenvalues ⋮ Exploiting symmetries in mathematical programming via orbital independence ⋮ Binary determinantal complexity ⋮ Characterization and classification of optimal LCD codes ⋮ Dichotomizing \(k\)-vertex-critical \(H\)-free graphs for \(H\) of order four ⋮ On digraphs with polygonal restricted numerical range ⋮ Oriented chromatic number of Cartesian products and strong products of paths ⋮ The QAP-polytope and the graph isomorphism problem ⋮ 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 ⋮ Further results on the classification of MDS codes ⋮ Constructions and bounds for mixed-dimension subspace codes ⋮ Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs ⋮ Generalized Ramsey numbers through adiabatic quantum optimization ⋮ Perturbations in a signed graph and its index ⋮ Non-embeddable quasi-residual quasi-symmetric designs ⋮ On the classification of quaternary optimal Hermitian LCD codes ⋮ On maximal relative projection constants ⋮ Optimal-depth sorting networks ⋮ On singular signed graphs with nullspace spanned by a full vector: signed nut graphs ⋮ Lower bounds for locally highly connected 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 ⋮ 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 ⋮ Enumerating partial Latin rectangles ⋮ A census of small transitive groups and vertex-transitive graphs ⋮ Switching in one-factorisations of complete graphs ⋮ There is no McLaughlin geometry ⋮ Steiner triple systems of order 21 with a transversal subdesign \(\mathrm{TD}(3, 6)\) ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ 16,051 formulas for Ottaviani's invariant of cubic threefolds ⋮ Variable symmetry breaking in numerical constraint problems ⋮ Affine symmetries of orbit polytopes ⋮ Turán numbers for odd wheels ⋮ Integer sequence discovery from small graphs ⋮ Network alignment by discrete Ollivier-Ricci flow ⋮ The sextuply shortened binary Golay code is optimal ⋮ On hypercube packings, blocking sets and a covering problem ⋮ On a family of highly regular graphs by Brouwer, Ivanov, and Klin ⋮ Computing subfields of number fields and applications to Galois group computations ⋮ Bipartite biregular Moore graphs ⋮ Enumeration of 2-level polytopes ⋮ A method for enumerating pairwise compatibility graphs with a given number of vertices ⋮ On the \(A_{\alpha}\)-characteristic polynomial of a graph ⋮ Obstructions to convexity in neural codes ⋮ The algebraic matroid of the finite unit norm tight frame (funtf) variety ⋮ Binomial edge ideals of bipartite graphs ⋮ Complex spherical codes with three inner products ⋮ The largest pure partial planes of order 6 have size 25 ⋮ \textsc{ToTo}: an open database for computation, storage and retrieval of tree decompositions ⋮ Counting Markov equivalence classes for DAG models on trees ⋮ Conflict vs causality in event structures ⋮ Minimal and canonical images ⋮ New refiners for permutation group search ⋮ 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 ⋮ Mappings of Butson-type Hadamard matrices ⋮ There is no (75,32,10,16) strongly regular graph ⋮ 4-cop-win graphs have at least 19 vertices ⋮ On Ryser's conjecture for linear intersecting multipartite hypergraphs ⋮ A new partial geometry \(\mathrm{pg}(5,5,2)\) ⋮ Common greedy wiring and rewiring heuristics do not guarantee maximum assortative graphs of given degree ⋮ Permutation group algorithms based on directed graphs ⋮ New quasi-symmetric designs by the Kramer-Mesner method ⋮ Disjoint direct product decompositions of permutation groups ⋮ Generating all finite modular lattices of a given size ⋮ New bounds for Ramsey numbers \(R ( K_k - e , K_l - e )\) ⋮ Traces ⋮ 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 ⋮ The Schläfli Fan ⋮ Kirkman triple systems with subsystems ⋮ A nonexistence certificate for projective planes of order ten with weight 15 codewords ⋮ 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

Uses Software

• nauty
• Saucy
• bliss
• geng
• conauto

Cites Work

• Errors in graph embedding algorithms
• Algorithms for a class of infinite permutation groups.
• A general backtrack algorithm for the isomorphism problem of combinatorial objects
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Conflict Propagation and Component Recursion for Canonical Labeling
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• The graph isomorphism disease
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs
• An Efficient Algorithm for Graph Isomorphism
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Practical graph isomorphism. II.