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

Ravi Janardan; Siu Wing Cheng

doi:10.1007/3-540-54099-7_10

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

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

Abstract

An efficient distributed algorithm is given for computing a single-source shortest path tree 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. The complexity of the algorithm ranges from O(n) to O(n²) as p ranges from 1 to Θ(n). The algorithm incorporates optimal distributed solutions to a number of interesting subproblems inducting: (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, an efficient message routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths.

Original language	English
Title of host publication	Distributed Algorithms - 4th International Workshop, Proceedings
Editors	Jan van Leeuwen, Nicola Santoro
Publisher	Springer Verlag
Pages	133-150
Number of pages	18
ISBN (Print)	9783540540991
DOIs	https://doi.org/10.1007/3-540-54099-7_10
Publication status	Published - 1991
Externally published	Yes
Event	4th International Workshop on Distributed Algorithms, WDAG 1990 - Bari, Italy Duration: 24 Sept 1990 → 26 Sept 1990

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	486 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th International Workshop on Distributed Algorithms, WDAG 1990
Country/Territory	Italy
City	Bari
Period	24/09/90 → 26/09/90

Bibliographical note

Publisher Copyright:
© 1991, Springer Verlag. All rights reserved.

Access to Document

10.1007/3-540-54099-7_10

Cite this

Janardan, R., & Cheng, S. W. (1991). Efficient distributed algorithms for single-source shortest paths and related problems on plane networks. In J. van Leeuwen, & N. Santoro (Eds.), Distributed Algorithms - 4th International Workshop, Proceedings (pp. 133-150). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 486 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-54099-7_10

Janardan, Ravi ; Cheng, Siu Wing. / Efficient distributed algorithms for single-source shortest paths and related problems on plane networks. Distributed Algorithms - 4th International Workshop, Proceedings. editor / Jan van Leeuwen ; Nicola Santoro. Springer Verlag, 1991. pp. 133-150 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2517c3baf54f49829b42df450edb7093,

title = "Efficient distributed algorithms for single-source shortest paths and related problems on plane networks",

abstract = "An efficient distributed algorithm is given for computing a single-source shortest path tree 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. The complexity of the algorithm ranges from O(n) to O(n2) as p ranges from 1 to Θ(n). The algorithm incorporates optimal distributed solutions to a number of interesting subproblems inducting: (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, an efficient message routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths.",

author = "Ravi Janardan and Cheng, \{Siu Wing\}",

note = "Publisher Copyright: {\textcopyright} 1991, Springer Verlag. All rights reserved.; 4th International Workshop on Distributed Algorithms, WDAG 1990 ; Conference date: 24-09-1990 Through 26-09-1990",

year = "1991",

doi = "10.1007/3-540-54099-7\_10",

language = "English",

isbn = "9783540540991",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "133--150",

editor = "\{van Leeuwen\}, Jan and Nicola Santoro",

booktitle = "Distributed Algorithms - 4th International Workshop, Proceedings",

}

Janardan, R & Cheng, SW 1991, Efficient distributed algorithms for single-source shortest paths and related problems on plane networks. in J van Leeuwen & N Santoro (eds), Distributed Algorithms - 4th International Workshop, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 486 LNCS, Springer Verlag, pp. 133-150, 4th International Workshop on Distributed Algorithms, WDAG 1990, Bari, Italy, 24/09/90. https://doi.org/10.1007/3-540-54099-7_10

Efficient distributed algorithms for single-source shortest paths and related problems on plane networks. / Janardan, Ravi; Cheng, Siu Wing.
Distributed Algorithms - 4th International Workshop, Proceedings. ed. / Jan van Leeuwen; Nicola Santoro. Springer Verlag, 1991. p. 133-150 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 486 LNCS).

Research output: Chapter in Book/Conference Proceeding/Report › Conference Paper published in a book › peer-review

TY - GEN

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

AU - Janardan, Ravi

AU - Cheng, Siu Wing

PY - 1991

Y1 - 1991

N2 - An efficient distributed algorithm is given for computing a single-source shortest path tree 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. The complexity of the algorithm ranges from O(n) to O(n2) as p ranges from 1 to Θ(n). The algorithm incorporates optimal distributed solutions to a number of interesting subproblems inducting: (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, an 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 a single-source shortest path tree 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. The complexity of the algorithm ranges from O(n) to O(n2) as p ranges from 1 to Θ(n). The algorithm incorporates optimal distributed solutions to a number of interesting subproblems inducting: (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, an efficient message routing scheme is presented which adapts to changing link conditions and routes along near-shortest paths.

UR - https://openalex.org/W1496451055

UR - https://www.scopus.com/pages/publications/85030641289

U2 - 10.1007/3-540-54099-7_10

DO - 10.1007/3-540-54099-7_10

M3 - Conference Paper published in a book

SN - 9783540540991

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 133

EP - 150

BT - Distributed Algorithms - 4th International Workshop, Proceedings

A2 - van Leeuwen, Jan

A2 - Santoro, Nicola

PB - Springer Verlag

T2 - 4th International Workshop on Distributed Algorithms, WDAG 1990

Y2 - 24 September 1990 through 26 September 1990

ER -

Janardan R, Cheng SW. Efficient distributed algorithms for single-source shortest paths and related problems on plane networks. In van Leeuwen J, Santoro N, editors, Distributed Algorithms - 4th International Workshop, Proceedings. Springer Verlag. 1991. p. 133-150. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-54099-7_10

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

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this