Finding k Shortest Paths in Cayley Graphs of Finite Groups
Dohan KimGraphs and Combinatorics 2024.
Abstract
We present a new method for finding k shortest paths between any two vertices in the Cayley graph Cay(G, S) of a finite group G with its generating set S closed under inverses. By using a reduced convergent rewriting system R for G, we first find the lexicographically minimal shortest path between two vertices in Cay(G, S). Then, by symmetrizing the length-preserving rules of R, we provide a polynomial time algorithm (in the size of certain rewrite rules, the lexicographically minimal shortest path, and k) for finding k shortest paths between two vertices in Cay(G, S). Our implementation of finding k shortest paths between two vertices in Cay(G, S) is also discussed.
BibTeX
@article{DBLP:journals/gc/Kim24,
author = {Dohan Kim},
title = {Finding k Shortest Paths in Cayley Graphs of Finite Groups},
journal = {Graphs Comb.},
volume = {40},
number = {6},
pages = {120},
year = {2024},
url = {https://doi.org/10.1007/s00373-024-02852-y},
doi = {10.1007/S00373-024-02852-Y},
timestamp = {Sun, 22 Dec 2024 15:48:58 +0100},
biburl = {https://dblp.org/rec/journals/gc/Kim24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}