Linear time algorithms for Abelian group isomorphism and related problems

DOI10.1016/j.jcss.2007.03.013zbMath1165.68036OpenAlexW2077723005MaRDI QIDQ2643019

Telikepalli Kavitha

Publication date: 23 August 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.03.013

zbMATH Keywords

abelian group isomorphism complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Finite abelian groups (20K01) Software, source code, etc. for problems pertaining to group theory (20-04)

Related Items (11)

Algorithms for Group Isomorphism via Group Extensions and Cohomology ⋮ EFFICIENT ALGORITHMS FOR THE BASIS OF FINITE ABELIAN GROUPS ⋮ On isomorphism testing of groups with normal Hall subgroups ⋮ Space efficient representations of finite groups ⋮ Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting) ⋮ Compact data structures for Dedekind groups and finite rings ⋮ Improved Algorithms for Alternating Matrix Space Isometry: From Theory to Practice ⋮ Beating the generator-enumeration bound for \(p\)-group isomorphism ⋮ Testing commutativity of a group and the power of randomization ⋮ Linear and sublinear time algorithms for the basis of abelian groups ⋮ Nearly linear time isomorphism algorithms for some nonabelian group classes

Cites Work

• On isomorphism testing of a class of 2-nilpotent groups
• Graph isomorphism, general remarks
• An \(O(n)\) algorithm for Abelian \(p\)-group isomorphism and an \(O(n \log n)\) algorithm for Abelian group isomorphism
• Fast Monte Carlo algorithms for permutation groups
• Sublinear algorithms for testing monotone and unimodal distributions
• Some new upper bounds on the generation of prime numbers
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• On the n^{log n} isomorphism technique (A Preliminary Report)
• On the complexity of some problems on groups input as multiplication tables
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Linear time algorithms for Abelian group isomorphism and related problems