Finding k shortest paths in Cayley graphs of finite groups

DOI10.1007/S00373-024-02852-YMaRDI QIDQ6640962zbMATH OpenFDO

Authors Dohan Kim

Publication date 20 November 2024

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

Cayley graphfinite groupstring rewriting system\(k\) shortest path

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Extremal problems in graph theory (05C35) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Paths and cycles (05C38) Finite generation, finite presentability, normal forms (diamond lemma, term-rewriting) (16S15)

Recommendations

• Low time complexity algorithms for path computation in Cayley graphs
• An algorithm for finding minimal generating sets of finite groups
• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles
• Diameter search algorithms for directed Cayley graphs

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 1241632 (Why is no real title available?)
• scientific article; zbMATH DE number 534859 (Why is no real title available?)
• scientific article; zbMATH DE number 2038382 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 789389 (Why is no real title available?)
• A group-theoretic model for symmetric interconnection networks
• Combinatorics of Coxeter Groups
• Construction of defining relators for finite groups
• Finite complete rewriting systems for groups
• Fundamental algorithms for permutation groups
• Geodesic rewriting systems and pregroups
• Implementation and Analysis of the Todd-Coxeter Algorithm
• Introduction to algorithms
• Low time complexity algorithms for path computation in Cayley graphs
• On the number of reduced decompositions of elements of Coxeter groups
• Presentations of groups generated by transpositions
• Processor interconnection networks from Cayley graphs
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• Rewriting systems of Coxeter groups
• Sorting on graphs by adjacent swaps using permutation groups
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The number of shortest paths in the \((n, k)\)-star graph
• The number of shortest paths in the arrangement graph
• There is no optimal routing policy for the torus.

This page was built for publication: Finding \(k\) shortest paths in Cayley graphs of finite groups

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