Generic case complexity of the graph isomorphism problem

DOI10.1515/GCC-2016-0008MaRDI QIDQ285911zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov, Gennady 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 distributiongraph isomorphismbinomial random graphgeneric algorithmLegendre polynomial

Mathematics Subject Classification ID

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

Recommendations

• On the generic complexity of the searching graph isomorphism problem
• Random Graph Isomorphism
• Testing Graph Isomorphism
• Search problems with a promise and graph isomorphism
• Fast canonical labeling of random subgraphs

Cites work

• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3917336 (Why is no real title available?)
• scientific article; zbMATH DE number 3485662 (Why is no real title available?)
• scientific article; zbMATH DE number 3516003 (Why is no real title available?)
• scientific article; zbMATH DE number 3575633 (Why is no real title available?)
• scientific article; zbMATH DE number 1246226 (Why is no real title available?)
• scientific article; zbMATH DE number 3373676 (Why is no real title available?)
• scientific article; zbMATH DE number 3080938 (Why is no real title available?)
• Almost every graph is vertex-oblique
• Average-Case Complexity
• Generic complexity of undecidable problems
• Group-theoretic algorithms and graph isomorphism
• On Extreme Metric Characteristics of a Random Graph. II. Limit Distributions
• Random Graph Isomorphism
• The graph isomorphism disease

Cited in

(2)

• scientific article; zbMATH DE number 512923 (Why is no real title available?)
• On the generic complexity of the searching graph isomorphism problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285911)