Efficient distributed algorithms for computing shortest pairs of maximally disjoint paths in communication networks
- 1 January 1991
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1214-1219 vol.3
- https://doi.org/10.1109/infcom.1991.147642
Abstract
Distributed algorithms are presented for finding two maximally disjoint paths of minimum total length from each possible source node to a destination, including both node-disjoint and link-disjoint versions of the algorithm. A synchronous algorithm having communication complexity O( mod E mod log D+ mod mod V mod D) and time complexity O( mod V mod W), where mod V mod and mod E mod denote the number of nodes and links in G, W is the maximum link length, and D is the depth of a shortest-path spanning tree directed toward the destination, is presented. For the important case W=O(1), the time complexity becomes O( mod V mod ). In this case, the asynchronous algorithm obtained by applying Synchronizer alpha of B. Awerbuch (1987) has communication complexity O( mod E mod V mod ) and time complexity O( mod V mod ). Serial, centralized versions of the algorithms with time complexity O( mod E mod + mod V mod log mod V mod ) and space complexity O( mod E mod ) are also presented.Keywords
This publication has 6 references indexed in Scilit:
- The Multi-Tree Approach To Reliability In Distributed NetworksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Reducing complexities of the distributed max‐flow and breadth‐first‐search algorithms by means of network synchronizationNetworks, 1985
- Complexity of network synchronizationJournal of the ACM, 1985
- A new distributed Depth-First-Search algorithmInformation Processing Letters, 1985
- A quick method for finding shortest pairs of disjoint pathsNetworks, 1984
- Disjoint paths in a networkNetworks, 1974