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

traces graph isomorphism partition refinement nauty canonical 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

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, Independence Equivalence Classes of Paths and Cycles, A proof system for graph (non)-isomorphism verification, Towards Efficient Normalizers of Primitive Groups, Isomorphism and Invariants of Parallelisms of Projective Spaces, Algebraic Polytopes in Normaliz, The Classification of Subfactors with Index at Most 5\frac{1}4, Nonexistence Certificates for Ovals in a Projective Plane of Order Ten, On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness, The complement problem for linklessly embeddable graphs, Trinajstić Index, Computation of new diagonal graph Ramsey numbers, Eternal domination and clique covering, The minimality of the Georges–Kelmans graph, CONICS IN SEXTIC -SURFACES IN, Small minimal $(3, 3)$-Ramsey graphs, Lower bounding the Folkman numbers $F_v(a_1, ..., a_s; m - 1)$, Switching for Small Strongly Regular Graphs, The Optimal Packing of Eight Points in the Real Projective Plane, Symmetry-driven network reconstruction through pseudobalanced coloring optimization, Computing Autotopism Groups of Partial Latin Rectangles, Handling symmetries in mixed-integer semidefinite programs, Breaking symmetries with high dimensional graph invariants and their combination, Enumerating Steiner triple systems, Cohen-Macaulay binomial edge ideals of small graphs, Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications, The smallest hard trees, The smallest 5-chromatic tournament, On the multiplicities of distance Laplacian eigenvalues, Regular graphs of degree at most four that allow two distinct eigenvalues, Totally symmetric quasigroups of order 16, A taxonomy for similarity metrics between Markov decision processes, Making the census of cubic vertex transitive graphs searchable and FAIR, Selecting energy efficient inputs using graph structure, An Isomorphism-Invariant Distance Function on Propositional Formulas in CNF, Polytope volume in Normaliz, Modular rewritable Petri nets: an efficient model for dynamic distributed systems, Complete minors in complements of nonseparating planar graphs, Graphs isomorphisms under edge-replacements and the family of amoebas, Statistics of Feynman amplitudes in $\phi^4$-theory, Enumeration of Latin squares with conjugate symmetry, 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, \texttt{tapir}: a tool for topologies, amplitudes, partial fraction decomposition and input for reductions, pySecDec: a toolbox for the numerical evaluation of multi-scale integrals, Are hitting formulas hard for resolution?, On linear algebraic algorithms for the subgraph matching problem and its variants, Incomplete pairwise comparison matrices based on graphs with average degree approximately 3, Comparison of Atom Maps, Wheels: a new criterion for non-convexity of neural codes, Realizable cycle structures in digraphs, Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians, Spectral theory of the non-backtracking Laplacian for graphs, A walk-regular graph, cospectral to its complement, need not be strongly regular, Classification of minimal blocking sets in PG(2,9), Cographs and 1-sums, A Note on Universal Point Sets for Planar Graphs, Construction of All Minimal Edge Extensions of the Graph with Isomorphism Rejection, Unnamed Item, Unnamed Item, Lights Out On A Random Graph, Short certificates for chromatic equivalence, Constructing Hard Examples for Graph Isomorphism, Unnamed Item, Edge crossings in random linear arrangements, Unnamed Item, Spectrally Robust Graph Isomorphism, Graph Similarity and Approximate Isomorphism, COMPARISON OF SUFFICIENT DEGREE BASED CONDITIONS FOR HAMILTONIAN GRAPH, CONSTRUCTING ALL NONISOMORPHIC SUPERGRAPHS WITH ISOMORPHISM REJECTION, Finding the Hardest Formulas for Resolution, Constructions of cospectral graphs with different zero forcing numbers, Reconstruction of small graphs and digraphs, Classification of Graeco-Latin Cubes, Benchmark Graphs for Practical Graph Isomorphism, Unnamed Item, Unnamed Item, Integer Programming for Classifying Orthogonal Arrays, An adaptive prefix-assignment technique for symmetry reduction, A class of Ramsey-extremal hypergraphs, Graphs with few hamiltonian cycles, On the enumeration of minimal non-pairwise compatibility graphs, On the enumeration of minimal non-pairwise compatibility graphs, On Weisfeiler-Leman invariance: subgraph counts and related graph properties, Construction of All Nonisomorphic Minimal Vertex Extensions of the Graph by the Method of Canonical Representatives, Smallest snarks with oddness 4 and cyclic connectivity 4 have order 44, The Power of the Weisfeiler-Leman Algorithm to Decompose Graphs, A Generic Framework for Engineering Graph Canonization Algorithms, Unnamed Item, Computing modular data for pointed fusion categories, Transitive Tournament Tilings in Oriented Graphs with Large Minimum Total Degree, A graph theoretical analysis of the number of edges in k-dense graphs, On L-shaped point set embeddings of trees: first non-embeddable examples, Symmetry Reduction to Optimize a Graph-based Polynomial From Queueing Theory, Isomorphism Test for Digraphs with Weighted Edges., Relating centralities in graphs and the principal eigenvector of its distance matrix, The Power of the Weisfeiler--Leman Algorithm to Decompose Graphs, Ordering trees by $\alpha$-index, Colouring problems for symmetric configurations with block size 3, Group divisible designs with block size 4 and group sizes 2 and 5, The maximum number of columns in E(s2) $\,E({s}^{2})$‐optimal supersaturated designs with 16 rows and smax=4 ${s}_{{\rm{\max }}}=4$ is 60, Sparse Steiner triple systems of order 21, Quaternary complex Hadamard matrices of order 18, Intersecting and 2‐intersecting hypergraphs with maximal covering number: The Erdős–Lovász theme revisited, Hadamard matrices of orders 60 and 64 with automorphisms of orders 29 and 31, Enumeration of sets of mutually orthogonal Latin rectangles, A census of small Schurian association schemes, Existence of regular nut graphs and the fowler construction, K₂‐Hamiltonian graphs: II, The classification of orthogonal arrays $\mathrm{OA}(2048,14,2,7)$ and some completely regular codes, On the connectivity and the diameter of betweenness-uniform graphs, On the bivariate permanent polynomials of graphs, Isotropic matroids. III: Connectivity, Regularity and planarity of token graphs, The uniqueness of a distance-regular graph with intersection array $\{32,27,8,1;1,4,27,32\}$ and related results, Plurigraph coloring and scheduling problems, Small $f$-vectors of 3-spheres and of 4-polytopes, Exhaustive Generation of k-Critical $${\mathcal H}$$ -Free Graphs, Classification of MDS Codes over Small Alphabets, Orbital Independence in Symmetric Mathematical Programs, Enumerating Neighborly Polytopes and Oriented Matroids, Tight lower and upper bounds for the complexity of canonical colour refinement, Unnamed Item, Structural and computational results on platypus graphs, Minimum spanning tree cycle intersection problem, The SU(3) spin model with chemical potential by series expansion techniques, Combinatorial reductions for the Stanley depth of $I$ and $S/I$, Non-Hamiltonian graphs in which every edge-contracted subgraph is Hamiltonian, Minimal extending sets in tournaments, Almost equitable partitions and new necessary conditions for network controllability, Generating irreducible copositive matrices using the stable set problem, Baby-step giant-step algorithms for the symmetric group, $c_2$ invariants of hourglass chains via quadratic denominator reduction, Coarse-grained entanglement classification through orthogonal arrays, Graphs Identified by Logics with Counting, On the Number of Synchronizing Colorings of Digraphs, Counting orientations of graphs with no strongly connected tournaments, Filtering graphs to check isomorphism and extracting mapping by using the conductance electrical model, Finding the symmetry group of an LP with equality constraints and its application to classifying orthogonal arrays, Recursive computation of Feynman periods, Polynomial reconstruction of signed graphs whose least eigenvalue is close to -2, Logic Programming with Graph Automorphism: Integratingnautywith Prolog (Tool Description), Quantum and non-signalling graph isomorphisms, On tail dependence matrices. The realization problem for parametric families, A model for finding transition-minors, Packing, partitioning, and covering symresacks, On some edge Folkman numbers, small and large, Counting frequent patterns in large labeled graphs: a hypergraph-based approach, Group divisible designs with block size 4 where the group sizes are congruent to $1 \bmod 3$, Intersection graph of maximal stars, On the Laplacian spread of digraphs, Towards detecting structural branching and cyclicity in graphs: a polynomial-based approach, Equimatchable Regular Graphs, Improved bounds for hypohamiltonian graphs, Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting), Hyperbolic Triangular Buildings Without Periodic Planes of Genus 2, Symmetry Breaking Constraints for the Minimum Deficiency Problem, A note on universal point sets for planar graphs, On the seven non-isomorphic solutions of the fifteen schoolgirl problem, DiscreteZOO: a fingerprint database of discrete objects, Unnamed Item, Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results, Generalized spectral characterization of mixed graphs, Solving computational problems in the theory of word-representable graphs, Star-critical Ramsey numbers for cycles versus $K_4$, Biangular lines revisited, Order nine MMIK graphs, Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic, Group theory on quantum Boltzmann machine, The chromatic number of the square of the $8$-cube, Cops and robbers on $2K_2$-free graphs, The cone of quasi-semimetrics and exponent matrices of tiled orders, Generating symmetric graphs, 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, Unnamed Item, 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, Enumeration of MOLS of small order, Constructing unlabelled lattices, Obstructions for three-coloring graphs without induced paths on six vertices, Iterative Equitable Partition of Graph as a Model of Constant Structure Discrete Time Closed Semantic System, Error Thresholds for Arbitrary Pauli Noise, Automorphism groups of some families of bipartite graphs, On the volumes and affine types of trades, Borderenergetic Graphs of Order 12, An Enumeration of Certain Projective Ternary Two-Weight Codes, On the upper embedding of symmetric configurations with block size 3, Hamiltonian Maker–Breaker Games on Small Graphs, Partial linear spaces with a rank 3 affine primitive group of automorphisms, Improved Static Symmetry Breaking for SAT, Computing Maximum Unavoidable Subgraphs Using SAT Solvers, Refining invariants for computing autotopism groups of partial Latin rectangles, On unbalanced Boolean functions with best correlation immunity, Generalized permanental polynomials of graphs, $k$-majority digraphs and the hardness of voting with a constant number of voters, On the minimum leaf number of cubic graphs, Unnamed Item, Unnamed Item, Calculating the symmetry number of flexible sphere clusters, Optimal packings of two to four equal circles on any flat torus, Constraints for symmetry breaking in graph representation, Novel techniques to speed up the computation of the automorphism group of a graph, The minimum number of minimal codewords in an $[n, k$-code and in graphic codes], Algorithms for finding generalized minimum aberration designs, Distinguishing graphs with zeta functions and generalized spectra, On the independence number of $(3, 3)$-Ramsey graphs and the Folkman number $F_e(3, 3; 4)$, Exhaustive search for snake-in-the-box codes

Uses Software

Cites Work