Testing whether the lifted group splits

angleški

2016

letnik 11, številka 1

algoritmi   dvignjene grupe   grafi

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Naj se grupa avtomorfizmov dvigne vzdolž regularne krovne projekcije povezanih grafov, podane kombinatorično z napetostmi. Tedaj so podatki, ki določajo dvignjeno grupo in njeno delovanje, prav tako zakodirani s pomočjo napetosti. Ustrezni algoritem za testiranje, ali je dvignjena grupa razcepna razširitev grupe krovnih transformacij, je bil nedavno predstavljen v primeru, ko je grupa krovnih transformacij rešljiva. Sestoji iz dekomponiranja krova v zaporedje krovov z elementarnimi abelovimi grupami krovnih transformacij, in induktivnega reševanja problema na vsakem elementarno abelovem koraku. Čeprav eksplicitna konstrukcija dvignjene grupe ni potrebna, algoritem vseeno vključuje časovno in prostorsko zahtevne konstrukcije določenih podgrup v dvignjeni grupi na vsakem koraku z izjemo zadnjega. V tem članku predstavimo izboljšano verzijo algoritma, ki se povsem izogne takšnim konstrukcijam. Iz porazdelitve napetosti najprej izračunamo šibko delovanje in faktorsko množico, ki določata dvignjeno grupo, nato pa izpeljemo test tako, da izluščimo potrebno informacijo samo iz ustreznih šibkih delovanj in faktorskih množic na vsakem koraku. Eksperimentalno primerjamo to in prejšnjo verzijo algoritma.

29.05.2020