The difficulty of testing for isomorphism against a graph that is given in advance

DOI10.1145/1007352.1007415MaRDI QIDQ3580984zbMATH OpenOpenAlexFDO

Authors Eldar Fischer

Publication date 15 August 2010

Published in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1007352.1007415

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Testing Graph Isomorphism
• The query complexity of graph isomorphism: bypassing distribution testing lower bounds
• Nearly tight bounds for testing function isomorphism
• Testing graph blow-up

Cited in

(4)

• The query complexity of graph isomorphism: bypassing distribution testing lower bounds
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Partially symmetric functions are efficiently isomorphism testable
• Testing Graph Isomorphism

This page was built for publication: The difficulty of testing for isomorphism against a graph that is given in advance

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