Low time complexity algorithms for path computation in Cayley graphs

DOI10.1016/j.dam.2018.12.005zbMath1409.05099OpenAlexW2906497735WikidataQ128714114 ScholiaQ128714114MaRDI QIDQ1735699

L. Fàbrega, P. Vilà, D. Aguirre-Guerrero, Guillaume Ducoffe, 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

Cayley graphsinterconnection networkspath computation\(K\)-shortest paths

Mathematics Subject Classification ID

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

Related Items (1)

Using semidirect products of groups to build classes of interconnection networks

Uses Software

• kbmag

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the construction of all shortest vertex-disjoint paths in Cayley graphs of abelian groups
• Symmetric Property and Reliability of Balanced Hypercube
• A group-theoretic model for symmetric interconnection networks
• A Scheme for Fast Parallel Communication
• Finding the k Shortest Paths
• Finding the K Shortest Loopless Paths in a Network

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