Nearly Linear Time Isomorphism Algorithms for Some Nonabelian Group Classes
| Autor: | Bireswar Das, Shivdutt Sharma |
|---|---|
| Přispěvatelé: | International Computer Science Symposium in Russia (CSR-2019 |
| Rok vydání: | 2020 |
| Předmět: |
Group (mathematics)
020207 software engineering 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Computational Theory and Mathematics 010201 computation theory & mathematics Theory of computation 0202 electrical engineering electronic engineering information engineering Isomorphism Abelian group Algorithm Time complexity Mathematics |
| Zdroj: | Theory of Computing Systems. 65:497-514 |
| ISSN: | 1433-0490 1432-4350 |
| DOI: | 10.1007/s00224-020-10010-z |
| Popis: | The isomorphism problem for groups, when the groups are given by their Cayley tables is a well-studied problem. This problem has been studied for various restricted classes of groups. Kavitha gave a linear time isomorphism algorithm for abelian groups (JCSS 2007). Although there are isomorphism algorithms for certain nonabelian group classes represented by their Cayley tables, the complexities of those algorithms are usually super-linear. In this paper, we design linear and nearly linear time isomorphism algorithms for some nonabelian groups. More precisely |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink