Finding k shortest paths in Cayley graphs of finite groups

DOI10.1007/S00373-024-02852-YMaRDI QIDQ6640962FDOQ6640962

Authors: Dohan Kim 

Publication date: 20 November 2024

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

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

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)

Cites Work

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

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)