Recognizing circulant graphs of prime order in polynomial time
A digraph can be regarded as a pair \((X;\gamma)\), where \(X\) is a finite set and \(\gamma\) is a binary relation on \(X\). The Weisfeiler-Leman algorithm in time \(O(| X|^3\log(| X|))\) yields the minimal coherent configuration \((X;\Gamma)\), where \(\Gamma\) contains \(\gamma\) [\textit{Babel, Baumann, Lüdecke} and \textit{Tinhofer}, STABCOL: Graph isomorphism testing based on the Weisfeiler-Leman algorithm. TUM-M9702, Munich, 45 p. (1997)]. There is an open problem to recognize the circulant property of digraphs \(X\) with an algorithm with time-complexity polynomial in \(X\). The authors present such an algorithm when \(| X| = p\), a prime, with time-complexity at most \(O(p^5\ln(p)^2)\). They start with the above coherent configuration (in this case, association scheme), and then utilize favorable facts on permutation groups and association schemes when \(| X|\) is a prime \(p\).
- Symmetry properties of chordal rings of degree 3
- On the structure property of PCR's adjacency graph with a prime order and its application of constructing M-sequences
- On automorphism groups of circulant digraphs of square-free order
- Finding the automorphism group of a circulant association scheme in polynomial time
- Circulant graphs: efficient recognizing and isomorphism testing
- Searching for (near) optimal codes
- Circulant graphs: recognizing and isomorphism testing in polynomial time
- scientific article; zbMATH DE number 7310081 (Why is no real title available?)
- Powers of cycles, powers of paths, and distance graphs
- Recognizing hyperelliptic graphs in polynomial time
- Colouring clique-hypergraphs of circulant graphs
- The Weisfeiler-Leman algorithm and recognition of graph properties
- The Weisfeiler-Leman algorithm and recognition of graph properties
- Recognizing circulant graphs in polynomial time: An application of association schemes
- On the WL-dimension of circulant graphs of prime power order
- Combinatorial refinement on circulant graphs
This page was built for publication: Recognizing circulant graphs of prime order in polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1386147)
