Random Graph Isomorphism
From MaRDI portal
Publication:3901544
DOI10.1137/0209047zbMath0454.05038OpenAlexW2051748083WikidataQ105673110 ScholiaQ105673110MaRDI QIDQ3901544
László Babai, Stanley M. Selkow
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209047
Related Items (66)
Finite Variable Logics in Descriptive Complexity Theory ⋮ On the Combinatorial Power of the Weisfeiler-Lehman Algorithm ⋮ On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness ⋮ Generic case complexity of the graph isomorphism problem ⋮ New invariants for the graph isomorphism problem ⋮ Fast canonical labeling of random subgraphs ⋮ On the robustness of the metric dimension of grid graphs to adding a single edge ⋮ Canonization for two variables and puzzles on the square ⋮ Generic complexity of the membership problem for semigroups of integer matrices ⋮ Tight lower and upper bounds for the complexity of canonical colour refinement ⋮ How to define a linear order on finite models ⋮ Almost every graph is vertex-oblique ⋮ Efficient random graph matching via degree profiles ⋮ Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism ⋮ Graph isomorphism, color refinement, and compactness ⋮ Graphs Identified by Logics with Counting ⋮ On Tinhofer’s Linear Programming Approach to Isomorphism Testing ⋮ On the Power of Color Refinement ⋮ On anti-stochastic properties of unlabeled graphs ⋮ Exact matching of random graphs with constant correlation ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Quantum and non-signalling graph isomorphisms ⋮ List-distinguishing Cartesian products of cliques ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Asymptotic theory in network models with covariates and a growing number of node parameters ⋮ Theory of graph neural networks: representation and learning ⋮ Group-theoretic generalisations of vertex and edge connectivities ⋮ Concerning the complexity of deciding isomorphism of block designs ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search ⋮ Malleability of complex networks ⋮ Isomorphism for random \(k\)-uniform hypergraphs ⋮ Isomorphism testing via polynomial-time graph extensions ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice ⋮ Expected parallel time and sequential space complexity of graph and digraph problems ⋮ Improved random graph isomorphism ⋮ On leaf permutative theories and occurrence permutation groups ⋮ On the power of combinatorial and spectral invariants ⋮ An optimal lower bound on the number of variables for graph identification ⋮ On the Weisfeiler-Leman dimension of fractional packing ⋮ On the complexity of deduction modulo leaf permutative equations ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ Descriptive complexity of graph spectra ⋮ Unnamed Item ⋮ Hashing and canonicalizing Notation 3 graphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ Metric dimension of critical Galton-Watson trees and linear preferential attachment trees ⋮ Topological variability of collectives and its import for social epistemology ⋮ An Average Case NP-complete Graph Colouring Problem ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ A graph isomorphism algorithm for object recognition ⋮ Cryptanalysis and improvements on some graph-based authentication schemes ⋮ Approximate lumpability for Markovian agent-based models using local symmetries ⋮ Randomised algorithms ⋮ On the local distinguishing numbers of cycles ⋮ Fractional isomorphism of graphons ⋮ Almost Everywhere Equivalence of Logics in Finite Model Theory ⋮ Sherali-Adams relaxations of graph isomorphism polytopes ⋮ Graph isomorphism problem ⋮ Random Models and Analyses for Chemical Graphs ⋮ On the limiting distribution of the metric dimension for random forests ⋮ Graph recurrence ⋮ On the Rigidity of Sparse Random Graphs
This page was built for publication: Random Graph Isomorphism
