Testing isomorphism of circulant objects in polynomial time

DOI10.1016/J.JCTA.2019.105128zbMATH Open1428.05222arXiv1812.06246OpenAlexW2971392181MaRDI QIDQ2010626FDOQ2010626

Authors: Mikhail Muzychuk, Ilya Ponomarenko 

Publication date: 27 November 2019

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $frakK$ be a class of combinatorial objects invariant with respect to a given regular cyclic group. It is proved that the isomorphism of any two objects $X,YinfrakK$ can be tested in polynomial time in sizes of $X$ and $Y$.

Full work available at URL: https://arxiv.org/abs/1812.06246

Recommendations

• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Finding a cycle base of a permutation group in polynomial time
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Isomorphism testing for circulant graphs \(C_n (a, b)\)
• Testing isomorphism of central Cayley graphs over almost simple groups in polynomial time

zbMATH Keywords

graph isomorphism problemcirculant combinatorial object

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Isomorphism problem for a class of point-symmetric structures
• Isomorphism problem for relational structures with a cyclic automorphism
• A solution of the isomorphism problem for circulant graphs
• A polynomial bound for the orders of primitive solvable groups
• Multipliers and generalized multipliers of cyclic objects and cyclic codes
• On the isomorphism problem for cyclic combinatorial objects
• Isomorphism of graphs which are pairwise k-separable
• On Ádám's conjecture for circulant graphs
• A solution of an equivalence problem for semisimple cyclic codes
• Isomorphisms of cyclic combinatorial objects
• The equivalence of two cyclic objects on \(pq\) elements
• The Cayley isomorphism property for Cayley maps
• Cyclic groups are CI-groups for balanced configurations
• A unifying method for the design of algorithms canonizing combinatorial objects

Cited In (9)

• Testing set proportionality and the Ádám isomorphism of circulant graphs
• Isomorphism testing for circulant graphs \(C_n (a, b)\)
• Combinatorial refinement on circulant graphs
• Finding a cycle base of a permutation group in polynomial time
• Polynomial time recognition and isomorphism testing for cyclic tournaments
• Testing isomorphism of circulant objects in polynomial time
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Polynomial time recognition and testing of isomorphism of cyclic tournaments
• Finding the automorphism group of a circulant association scheme in polynomial time

This page was built for publication: Testing isomorphism of circulant objects in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2010626)