Random Graph Isomorphism
From MaRDI portal
Publication:3901544
DOI10.1137/0209047zbMath0454.05038WikidataQ105673110 ScholiaQ105673110MaRDI QIDQ3901544
László Babai, Stanley M. Selkow, Paul 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
Related Items
On the complexity of deduction modulo leaf permutative equations, Graph theory (algorithmic, algebraic, and metric problems), Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements, Almost every graph is vertex-oblique, Optimal assignment of task modules with precedence for distributed processing by graph matching and state-space search, Improved random graph isomorphism, On the power of combinatorial and spectral invariants, Hashing and canonicalizing Notation 3 graphs, Graph isomorphism problem, Concerning the complexity of deciding isomorphism of block designs, Expected parallel time and sequential space complexity of graph and digraph problems, An optimal lower bound on the number of variables for graph identification, A graph isomorphism algorithm for object recognition, On the local distinguishing numbers of cycles, Canonization for two variables and puzzles on the square, How to define a linear order on finite models, Randomised algorithms, Graph recurrence, Almost Everywhere Equivalence of Logics in Finite Model Theory, A Logspace Algorithm for Partial 2-Tree Canonization, Finite Variable Logics in Descriptive Complexity Theory
