Diameter Search Algorithms for Directed Cayley Graphs

Simple item page
dc.contributor.authorOlshevskyi, Maksym
dc.date.accessioned2022-05-27T23:34:12Z
dc.date.available2022-05-27T23:34:12Z
dc.date.issued2021-05
dc.description.abstractIt is considered a well known diameter search problem for finite groups. It can be formulated as follows: find the maximum possible diameter of the group over its system of generators. The diameter of a group over a specific system of generators is the diameter of the corresponding Cayley graph. In the paper a closely related problem is considered. For a specific system of generators find the diameter of corresponding Cayley graph. It is shown that the last problem is polynomially reduced to the problem of searching the minimal decomposition of elements over a system of generators. It is proposed five algorithms to solve the diameter search problem: simple down search algorithm, fast down search algorithm, middle down search algorithms, homogeneous down search algorithm and homogeneous middle down search algorithm.en_US
dc.description.abstractРозглянуто добре відому задачу пошуку діаметра скінченної групи. Вона формулюється так: знайти найбільший серед діаметрів групи відносно її систем твірних. Діаметром групи є діаметр графа Келі, що будується на основі групи та її системи твірних. У цій роботі розглянуто підзадачу задачі пошуку діаметра групи, а саме, задачу знаходження діаметра групи відносно заданої системи твірних. Показано, що ця задача поліноміально зводиться до задачі пошуку мінімальних розкладів елементів. Для розв’язання задачі знаходження діаметра групи відносно заданої системи твірних запропоновано п'ять алгоритмів: простий алгоритм пошуку вниз, швидкий алгоритм пошуку вниз, серединний алгоритм пошуку вниз, однорідний алгоритм пошуку вниз та однорідний серединний алгоритм пошуку вниз. Перші два алгоритми є універсальними, а інші вимагають виконання додаткових умов на системи твірних. Для алгоритму серединного спуску введено поняття строго зростаючої системи твірних. За виконання цієї умови, пошук мінімальних розкладів потенційних найдовших розкладів можна почати одразу ж із певної множини. Введено окрему теорію однорідності. В ній розглядануто ряди груп та їх систем твірних, що задовольняють певним додатковим умовам. Введено властивість однорідності таких рядів та відношення еквівалентності їх елементів. Основною метою введення такого відношення є збереження розкладів її елементів в одному класі. Ця властивість дає можливість обраховувати мінімальний розклад лише для представника класу еквівалентності. Для алгоритмів однорідного пошуку вниз та однорідного серединного пошуку вниз необхідною умовою застосування є належність групи до однорідного генеративного ряду груп. Тоді задача знаходження мінімальних розкладів елементів зводиться до знаходження мінімальних розкладів представників класів еквіваленції. Показано, що всі описані алгоритми є коректними. Зроблено оцінки складності їх роботи.uk_UA
dc.identifier.citationOlshevskyi M. Diameter search algorithms for directed Cayley graphs / Maksym Olshevskyi // Могилянський математичний журнал. - 2021. - Т. 4. - С. 7-19. - https://doi.org/10.18523/2617-7080420217-19en_US
dc.identifier.issn2617-7080
dc.identifier.issn2663-0648
dc.identifier.urihttps://doi.org/10.18523/2617-7080420217-19
dc.identifier.urihttps://ekmair.ukma.edu.ua/handle/123456789/23011
dc.language.isoenuk_UA
dc.relation.sourceМогилянський математичний журналuk_UA
dc.statusfirst publisheden_US
dc.subjectCayley graphen_US
dc.subjectdiameter of groupen_US
dc.subjectsystem of generatorsen_US
dc.subjectarticleen_US
dc.subjectграф Келіuk_UA
dc.subjectдіаметр групиuk_UA
dc.subjectсистема твірнихuk_UA
dc.titleDiameter Search Algorithms for Directed Cayley Graphsen_US
dc.title.alternativeАлгоритми пошуку діаметра орієнтованих графів Келіuk_UA
dc.typeArticleuk_UA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Olshevskyi_Diameter_search_algorithms_for_directed_Cayley_graphs.pdf
Size:
324.83 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
7.54 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Том 4