-
The simultaneous conjugacy problem in the symmetric groupBrodnik, Andrej ; Malnič, Aleksander ; Požar, Rok, 1986-The transitive simultaneous conjugacy problem asks whether there exists a permutation ▫$\tau \in S_n$▫ such that ▫$b_j = \tau^{-1} a_j \tau$▫ holds for all ▫$j = 1,2, \ldots , d$▫, where ▫$a_1, a_2, ... \ldots , a_d$▫ and ▫$b_1, b_2, \ldots , b_d$▫ are given sequences of ▫$d$▫ permutations in ▫$S_n$▫, each of which generates a transitive subgroup of ▫$S_n$▫. As from mid 70' it has been known that the problem can be solved in ▫$O(dn^2)$▫ time. An algorithm with running time ▫$O(dn \log (dn))$▫, proposed in late 80', does not work correctly on all input data. In this paper we solve the transitive simultaneous conjugacy problem in ▫$O(n^2 \log d / \log n + dn\log n)$▫ time and ▫$O(n^{3/ 2} + dn)$▫ space. Experimental evaluation on random instances shows that the expected running time of our algorithm is considerably better, perhaps even nearly linear in ▫$n$▫ at given ▫$d$▫.Vir: Mathematics of computation. - ISSN 0025-5718 (Vol. 90, no. 332, Nov. 2021, str. 2977-2995)Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasleLeto - 2021Jezik - angleškiCOBISS.SI-ID - 61722371
Avtor
Brodnik, Andrej |
Malnič, Aleksander |
Požar, Rok, 1986-
Teme
deli in vladaj |
algoritem za hitro množenje |
izomorfizem grafov |
množenje permutacij |
problem simultane konjugacije |
iteracija |
divide-and-conquer |
fast multiplication algorithm |
graph isomorphism |
permutation multiplication |
simultaneous conjugacy problem |
truncated iteration |
GAP
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Brodnik, Andrej | 04967 |
Malnič, Aleksander | 02507 |
Požar, Rok, 1986- | 32026 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.