Title: | Recognizing and Testing Isomorphism of Cayley Graphs over an Abelian Group of Order 4p in Polynomial Time |
Other Titles: | Rozpoznání a testování izomorfismu Cayleyho grafů nad Abelovskými grupami řádu 4p |
Authors: | Nedela, Roman Ponomarenko, Ilia |
Citation: | NEDELA, R., PONOMARENKO, I. Recognizing and Testing Isomorphism of Cayley Graphs over an Abelian Group of Order 4p in Polynomial Time. In: Isomorphisms, Symmetry and Computations in Algebraic Graph Theory. Heidelberg: Springer, 2020. s. 195-218. ISBN 978-3-030-32807-8 , ISSN 2194-1009. |
Issue Date: | 2020 |
Publisher: | Springer |
Document type: | konferenční příspěvek conferenceObject |
URI: | 2-s2.0-85079093953 http://hdl.handle.net/11025/42391 |
ISBN: | 978-3-030-32807-8 |
ISSN: | 2194-1009 |
Keywords: | graf, grupa, algoritmus |
Keywords in different language: | graph, group, algorithm |
Abstract: | Skonstruujeme polynomiální algoritmus na rozpoznání a testování izomorfismu Cayleyho grafů nad Abelovskými grupami řádu 4p, kde p je prvočíslo. |
Abstract in different language: | We construct a polynomial-time algorithm that, for a graph X with 4p We construct a polynomial-time algorithm that for a graph X with 4p vertices (p is prime), finds (if any) a Cayley representation of X over the group C2 × C2 × Cp. This result, together with the known similar result for circulant graphs, shows that recognizing and testing isomorphism of Cayley graphs over an abelian group of order 4p can be done in polynomial time |
Rights: | Plný text není přístupný. © Springer |
Appears in Collections: | Konferenční příspěvky / Conference papers (NTIS) Konferenční příspěvky / Conference Papers (KMA) OBD |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ponomarenkonedela.pdf | 6,63 MB | Adobe PDF | View/Open Request a copy |
Please use this identifier to cite or link to this item:
http://hdl.handle.net/11025/42391
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.