Random Graph Isomorphism
From MaRDI portal
Publication:3901544
DOI10.1137/0209047zbMATH Open0454.05038OpenAlexW2051748083WikidataQ105673110 ScholiaQ105673110MaRDI QIDQ3901544FDOQ3901544
Authors: László Babai, Stanley Selkow, P. Erdős 
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
Recommendations
Cited In (74)
- Approximate lumpability for Markovian agent-based models using local symmetries
- Lower and upper bounds for numbers of linear regions of graph convolutional networks
- Canonization of a random circulant graph by counting walks
- An algorithm for optimal isomorphism between two random graphs
- Random models and analyses for chemical graphs
- Constraint satisfaction, graph isomorphism, and the pebbling comonad
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- A graphon perspective for fractional isomorphism
- An algorithm to recover shredded random matrices
- Theory of graph neural networks: representation and learning
- Title not available (Why is that?)
- Cutting planes width and the complexity of graph isomorphism refutations
- On isomorphism-invariant antistochastic properties of random graphs
- Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\)
- Constructing hard examples for graph isomorphism
- Power-law decay of the degree-sequence probabilities of multiple random graphs with application to graph isomorphism
- Generic complexity of the membership problem for semigroups of integer matrices
- Improved random graph isomorphism
- On the power of combinatorial and spectral invariants
- On leaf permutative theories and occurrence permutation groups
- Isomorphism for random \(k\)-uniform hypergraphs
- Tight lower and upper bounds for the complexity of canonical colour refinement
- On anti-stochastic properties of unlabeled graphs
- Canonization for two variables and puzzles on the square
- Quantum and non-signalling graph isomorphisms
- Cryptanalysis and improvements on some graph-based authentication schemes
- On Weisfeiler-Leman invariance: subgraph counts and related graph properties
- Asymptotic theory in network models with covariates and a growing number of node parameters
- On the complexity of deduction modulo leaf permutative equations
- Generic case complexity of the graph isomorphism problem
- Fast canonical labeling of random subgraphs
- On the local distinguishing numbers of cycles
- Graph theory (algorithmic, algebraic, and metric problems)
- Almost every graph is vertex-oblique
- On the Complexity of Isomorphism Problems for Tensors, Groups, and Polynomials I: Tensor Isomorphism-Completeness
- On the robustness of the metric dimension of grid graphs to adding a single edge
- Efficient random graph matching via degree profiles
- On the combinatorial power of the Weisfeiler-Lehman algorithm
- Malleability of complex networks
- Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
- Sherali-Adams relaxations of graph isomorphism polytopes
- Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
- Graphs identified by logics with counting
- New invariants for the graph isomorphism problem
- An optimal lower bound on the number of variables for graph identification
- On the Rigidity of Sparse Random Graphs
- On the limiting distribution of the metric dimension for random forests
- Group-theoretic generalisations of vertex and edge connectivities
- General linear group action on tensors: a candidate for post-quantum cryptography
- On the Weisfeiler-Leman dimension of fractional packing
- Graph isomorphism, color refinement, and compactness
- On Tinhofer's linear programming approach to isomorphism testing
- On the power of color refinement
- Concerning the complexity of deciding isomorphism of block designs
- Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice
- A non-factorial algorithm for canonical numbering of a graph
- Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search
- Topological variability of collectives and its import for social epistemology
- How to define a linear order on finite models
- Benchmark Graphs for Practical Graph Isomorphism
- Expected parallel time and sequential space complexity of graph and digraph problems
- Hashing and canonicalizing Notation 3 graphs
- A Logspace Algorithm for Partial 2-Tree Canonization
- Finite Variable Logics in Descriptive Complexity Theory
- Isomorphism testing via polynomial-time graph extensions
- Graph recurrence
- Graph isomorphism problem
- An Average Case NP-complete Graph Colouring Problem
- List-distinguishing Cartesian products of cliques
- Almost Everywhere Equivalence of Logics in Finite Model Theory
- Randomised algorithms
- A graph isomorphism algorithm for object recognition
- Fractional isomorphism of graphons
- Exact matching of random graphs with constant correlation
This page was built for publication: Random Graph Isomorphism
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3901544)
