DSpace
 

EPrints@IIT Delhi >
Faculty Research Publicatons  >
Computer Science and Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/294

Title: AnO(n) Algorithm for Abelianp-Group Isomorphism and anO(n log n) Algorithm for Abelian Group Isomorphism
Authors: Vikas, Narayan
Keywords: group isomorphism
multiplication tables
Abelian
algorithm
Issue Date: 1996
Citation: Journal of Computer and System Sciences, 53(1), 1-9
Abstract: The isomorphism problem for groups is to determine whether two finite groups are isomorphic. The groups are assumed to be epresented by their multiplication tables. Tarjan has shown that this problem can bedone in time O(nlog n+O(1)) for groups of cardinality n. Savage has claimed an algorithm for showing that if the groups are Abelian,isomorphism can be determined in time O(n2). We improve this bound and give an O(n log n) algorithm for Abelian group isomorphism.Further, we show that if the groups are Abelian p-groups then isomorphism can be determined in time O(n). We also show that the elementary divisor sequence for an Abelian group can be determined in time O(n log n) and for an Abelian p-group it can be determined in time O(n).
URI: http://eprint.iitd.ac.in/dspace/handle/2074/294
Appears in Collections:Computer Science and Engineering

Files in This Item:

File Description SizeFormat
vikasalg96.pdf326.14 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback