Název: | Recognizing and Testing Isomorphism of Cayley Graphs over an Abelian Group of Order 4p in Polynomial Time |
Další názvy: | Rozpoznání a testování izomorfismu Cayleyho grafů nad Abelovskými grupami řádu 4p |
Autoři: | Nedela, Roman Ponomarenko, Ilia |
Citace zdrojového dokumentu: | 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. |
Datum vydání: | 2020 |
Nakladatel: | Springer |
Typ dokumentu: | 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 |
Klíčová slova: | graf, grupa, algoritmus |
Klíčová slova v dalším jazyce: | graph, group, algorithm |
Abstrakt: | Skonstruujeme polynomiální algoritmus na rozpoznání a testování izomorfismu Cayleyho grafů nad Abelovskými grupami řádu 4p, kde p je prvočíslo. |
Abstrakt v dalším jazyce: | 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 |
Práva: | Plný text není přístupný. © Springer |
Vyskytuje se v kolekcích: | Konferenční příspěvky / Conference papers (NTIS) Konferenční příspěvky / Conference Papers (KMA) OBD |
Soubory připojené k záznamu:
Soubor | Velikost | Formát | |
---|---|---|---|
ponomarenkonedela.pdf | 6,63 MB | Adobe PDF | Zobrazit/otevřít Vyžádat kopii |
Použijte tento identifikátor k citaci nebo jako odkaz na tento záznam:
http://hdl.handle.net/11025/42391
Všechny záznamy v DSpace jsou chráněny autorskými právy, všechna práva vyhrazena.