Low time complexity algorithms for path computation in Cayley graphs

DOI10.1016/J.DAM.2018.12.005MaRDI QIDQ1735699zbMATH OpenOpenAlexWikidataFDO

Authors D. Aguirre-Guerrero, Guillaume Ducoffe, L. Fàbrega, P. Vilà, David Coudert

Publication date 28 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://hal.inria.fr/hal-01973608/file/cga_final.pdf

zbMATH Keywords

\(K\)-shortest pathsCayley graphsinterconnection networkspath computation

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• New methods for using Cayley graphs in interconnection networks
• Cayley fuzzy graphs on the fuzzy groups
• Representations and routing for Cayley graphs (computer networks)
• Shortest routing in trivalent Cayley graph network

Cites work

• A group-theoretic model for symmetric interconnection networks
• A Scheme for Fast Parallel Communication
• Finding the K Shortest Loopless Paths in a Network
• Finding the k Shortest Paths
• scientific article; zbMATH DE number 3758564 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• Symmetric Property and Reliability of Balanced Hypercube

Cited in

(3)

• Using semidirect products of groups to build classes of interconnection networks
• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• Finding k shortest paths in Cayley graphs of finite groups

Describes a project that uses

Uses Software

• kbmag

This page was built for publication: Low time complexity algorithms for path computation in Cayley graphs

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