A subquadratic algorithm for the simultaneous conjugacy problem

DOI10.1002/JGT.22798MaRDI QIDQ6057893zbMATH OpenOpenAlexFDO

Authors Andrej Brodnik, Aleksander Malnič, Rok Požar

Publication date 5 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

canonical labellinggraph isomorphismsimultaneous conjugacy problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Symmetric groups (20B30)

Abstract: The $d$-Simultaneous Conjugacy problem in the symmetric group $S_n$ asks whether there exists a permutation $auin{S}_n$ such that $b_j=a{u}^{-1}{a}_{j}au$ holds for all $j=1,2,ldots,d$, where $a_1,a_2,ldots,a_d$ and $b_1,b_2,ldots,b_d$ are given sequences of permutations in $S_n$. The time complexity of existing algorithms for solving the problem is $O(d{n}^2)$. We show that for a given positive integer $d$ the $d$-Simultaneous Conjugacy problem in $S_n$ can be solved in $o(n^2)$ time.

Recommendations

• The simultaneous conjugacy problem in the symmetric group
• scientific article; zbMATH DE number 3968860
• Sylow's theorem in polynomial time
• On simultaneous conjugation of permutations
• scientific article; zbMATH DE number 96386

Cites work

• A fast algorithm for testing isomorphism of permutation networks
• Computing stable epimorphisms onto finite groups
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 3585658 (Why is no real title available?)
• scientific article; zbMATH DE number 1849958 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Lifting graph automorphisms by voltage assignments
• Reconfiguration Algorithms for Interconnection Networks
• Regular homomorphisms and regular maps
• Smallest tetravalent half-arc-transitive graphs with the vertex-stabiliser isomorphic to the dihedral group of order 8
• Subcomplete generalizations of graph isomorphism
• The simultaneous conjugacy problem in the symmetric group

Cited in

(4)

• On simultaneous conjugation of permutations
• A subquadratic algorithm for minimum palindromic factorization
• The simultaneous conjugacy problem in the symmetric group
• Automorphisms and isomorphisms of maps in linear time

This page was built for publication: A subquadratic algorithm for the simultaneous conjugacy problem

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