Cayley graphs provide a group-theoretic model for designing and analyzing symmetric interconnection networks. In this paper, we give a sufficient condition for the existence of m vertex-disjoint shortest paths from one source vertex to other m (not necessarily distinct) destination vertices in a Cayley graph of an abelian group, where m≤n and n is the cardinality of a (group) generator of the abelian group. In addition, when the condition holds, the m vertex-disjoint shortest paths can be constructed in O(mn) time, which is optimal in the worst case when O(n)≤ the order of diameter. By applying our results, we can easily obtain the necessary and sufficient conditions, which can be verified in nearly optimal time, for the existence of all shortest vertex-disjoint paths in generalized hypercubes.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com