TY - JOUR

T1 - Efficient distributed algorithms for single-source shortest paths and related problems on plane networks

AU - Janardan, Ravi

AU - Cheng, Siu Wing

PY - 1992/6/1

Y1 - 1992/6/1

N2 - An efficient distributed algorithm is given for computing single-source shortest paths in an asynchronous planar network. The algorithm has message and time complexity O(pn) on an n-node network, where p is the smallest number of faces needed to cover all the nodes, taken over all possible plane embeddings of the network. Each node has only local information about the network, consisting of an ordered list of its incident edges in the embedding that realizes p and the name of the covering face that it belongs to. The complexity of the algorithm ranges from O(n) to O(n 2) as p ranges from 1 to Θ(n). The algorithm is more efficient than previous algorithms [A3], [F1] for a broad range of values for p; however, the algorithms in [A3] and [F1] do not require knowledge about the embedding. The single-source algorithm incorporates optimal distributed solutions to a number of interesting subproblems including: (i) decomposing the plane embedding into Θ(p) outerplane graphs with favorable properties; (ii) a single-source algorithm for outerplane graphs; and (iii) identifying any edge in an outerplane graph whose cost exceeds the distance between its endpoints. As an application, a communication-, time-, and space-efficient message-routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths.

AB - An efficient distributed algorithm is given for computing single-source shortest paths in an asynchronous planar network. The algorithm has message and time complexity O(pn) on an n-node network, where p is the smallest number of faces needed to cover all the nodes, taken over all possible plane embeddings of the network. Each node has only local information about the network, consisting of an ordered list of its incident edges in the embedding that realizes p and the name of the covering face that it belongs to. The complexity of the algorithm ranges from O(n) to O(n 2) as p ranges from 1 to Θ(n). The algorithm is more efficient than previous algorithms [A3], [F1] for a broad range of values for p; however, the algorithms in [A3] and [F1] do not require knowledge about the embedding. The single-source algorithm incorporates optimal distributed solutions to a number of interesting subproblems including: (i) decomposing the plane embedding into Θ(p) outerplane graphs with favorable properties; (ii) a single-source algorithm for outerplane graphs; and (iii) identifying any edge in an outerplane graph whose cost exceeds the distance between its endpoints. As an application, a communication-, time-, and space-efficient message-routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths.

UR - http://www.scopus.com/inward/record.url?scp=51249165061&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=51249165061&partnerID=8YFLogxK

U2 - 10.1007/BF02835831

DO - 10.1007/BF02835831

M3 - Article

AN - SCOPUS:51249165061

SN - 1432-4350

VL - 25

SP - 93

EP - 122

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -