Canonical form for graphs in quasipolynomial time: preliminary report

DOI10.1145/3313276.3316356MaRDI QIDQ5212862zbMATH OpenOpenAlexFDO

Authors László Babai

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

algorithmsgraphscomplexitygroup theoryisomorphismcanonical form

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Recommendations

• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphisms in quasi-polynomial time [after Babai and Luks, Weisfeiler-Leman,\ldots]
• scientific article; zbMATH DE number 867694
• A non-factorial algorithm for canonical numbering of a graph
• From Invariants to Canonization in Parallel

Cited in

(8)

• Computing Autotopism Groups of Partial Latin Rectangles
• When privacy fails, a formula describes an attack: a complete and compositional verification method for the applied \(\pi\)-calculus
• Graph isomorphism in quasipolynomial time (extended abstract)
• Quasipolynomiality of the Smallest Missing Induced Subgraph
• Quasipolynomial-time canonical form for steiner designs
• Algorithms for matrix code and alternating trilinear form equivalences via new isomorphism invariants
• Faster isomorphism for \(p\)-groups of class 2 and exponent \(p\)
• From Invariants to Canonization in Parallel

This page was built for publication: Canonical form for graphs in quasipolynomial time: preliminary report

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