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

Ravi Janardan, Siu Wing Cheng

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 (US)
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
State	Published - 1991
Event	4th International Workshop on Distributed Algorithms, WDAG 1990 - Bari, Italy Duration: Sep 24 1990 → Sep 26 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

Other

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

Bibliographical note

Funding Information:
1Research supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. The first author was also supported in part by NSF grant CCR-8808574. Authors' e-mail addresses: [email protected]; scheng~umn-cs.cs.umn.edu.

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

Publisher link

10.1007/3-540-54099-7_10

Find It

Find It at U of M Libraries

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

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/Report/Conference proceeding › Conference contribution

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, 9/24/90. https://doi.org/10.1007/3-540-54099-7_10

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

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{d633141952cd4e8f9ae6e0fbfc37ddd8,

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 = "Funding Information: 1Research supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. The first author was also supported in part by NSF grant CCR-8808574. Authors' e-mail addresses: [email protected]; scheng~umn-cs.cs.umn.edu. 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 (US)",

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",

}

TY - GEN

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

AU - Janardan, Ravi

AU - Cheng, Siu Wing

N1 - Funding Information: 1Research supported in part by a grant-in-aid of research from the Graduate School of the University of Minnesota. The first author was also supported in part by NSF grant CCR-8808574. Authors' e-mail addresses: [email protected]; scheng~umn-cs.cs.umn.edu. Publisher Copyright: © 1991, Springer Verlag. All rights reserved.

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 - http://www.scopus.com/inward/record.url?scp=85030641289&partnerID=8YFLogxK

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

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

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

M3 - Conference contribution

AN - SCOPUS:85030641289

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 -

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

Abstract

Publication series

Other

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this