Generic case complexity of the graph isomorphism problem

DOI10.1515/gcc-2016-0008zbMath1338.05140OpenAlexW2319423625MaRDI QIDQ285911

Alexander N. Rybalov, Guennadi A. Noskov

Publication date: 19 May 2016

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc-2016-0008

zbMATH Keywords

Poisson distributionLegendre polynomialgeneric algorithmgraph isomorphismbinomial random graph

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Determinants, permanents, traces, other special matrix functions (15A15) Paths and cycles (05C38) Eigenvalues, singular values, and eigenvectors (15A18)

Cites Work

• Almost every graph is vertex-oblique
• Group-theoretic algorithms and graph isomorphism
• Generic complexity of undecidable problems
• Average-Case Complexity
• Random Graph Isomorphism
• On Extreme Metric Characteristics of a Random Graph. II. Limit Distributions
• The graph isomorphism disease
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Generic case complexity of the graph isomorphism problem