University of Primorska University Library - all departments (UPUK)
-
Fast computation of the centralizer of a permutation group in the symmetric groupPožar, Rok, 1986-Let G be a permutation group acting on a set Ω. Best known algorithms for computing the centralizer of G in the symmetric group on Ω are all based on the same general approach that involves solving ... the following two fundamental problems: given a G-orbit Δ of size n, compute the centralizer of the restriction of G to Δ in the symmetric group on Δ; and given two G-orbits Δ and Δ′ each of size n, find an equivalence between the action of G restricted to Δ and the action of G restricted to Δ′ when one exists. If G is given by a generating set X, previous solutions to each of these two problems take O(|X|n2) time. In this paper, we first solve each fundamental problem in O(δn+|X|nlogn) time, where δ is the depth of the breadth-first-search Schreier tree for X rooted at some fixed vertex. For the important class of small-base groups G, we improve the theoretical worst-case time bound of our solutions to O(nlogcn+|X|nlogn) for some constant c. Moreover, if ⌈20log2n⌉ uniformly distributed random elements of G are given in advance, our solutions have, with probability at least 1−1/n, a running time of O(nlog2n+|X|nlogn). We then apply our solutions to obtain a more efficient algorithm for computing the centralizer of G in the symmetric group on Ω. In an experimental evaluation we demonstrate that it is substantially faster than previously known algorithms.Source: Journal of symbolic computation. - ISSN 0747-7171 (Vol. 123, art. 102287, jul./avg. 2024, str. 1-14)Type of material - article, component part ; adult, seriousPublish date - 2024Language - englishCOBISS.SI-ID - 181181699
Author
Požar, Rok, 1986-
Topics
algorithm |
centralizer |
decrease-and-conquer |
schreier tree |
permutation group |
algoritem |
centralizator |
zmanjšaj in vladaj |
Schreierjevo drevo |
permutacijska grupa
source: Journal of symbolic computation. - ISSN 0747-7171 (Vol. 123, art. 102287, jul./avg. 2024, str. 1-14)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
If the library membership card is not in the list,
add a new one.
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Požar, Rok, 1986- | 32026 |
Source: Personal bibliographies
and: SICRIS
Select pickup location:
Material pickup by post
Delivery address:
Address is missing from the member's data.
The address retrieval service is currently unavailable, please try again.
By clicking the "OK" button, you will confirm the pickup location selected above and complete the reservation process.
By clicking the "OK" button, you will confirm the above pickup location and delivery address, and complete the reservation process.
By clicking the "OK" button, you will confirm the address selected above and complete the reservation process.
Notification
Automatic login and reservation service currently not available. You can reserve the material on the Biblos portal or try again here later.
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
Pickup location | Material status | Reservation |
---|
Reservation in progress
Please wait a moment.
Reservation was successful.
Reservation failed.
Reservation...
Membership card:
Pickup location: