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

Ravi Janardan, Siu Wing Cheng

Research output: Chapter in Book/Report/Conference proceedingConference 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(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.

Original languageEnglish (US)
Title of host publicationDistributed Algorithms - 4th International Workshop, Proceedings
EditorsJan van Leeuwen, Nicola Santoro
PublisherSpringer Verlag
Pages133-150
Number of pages18
ISBN (Print)9783540540991
DOIs
StatePublished - 1991
Event4th International Workshop on Distributed Algorithms, WDAG 1990 - Bari, Italy
Duration: Sep 24 1990Sep 26 1990

Publication series

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

Other

Other4th International Workshop on Distributed Algorithms, WDAG 1990
CountryItaly
CityBari
Period9/24/909/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: janardan@umn-cs.cs.umn.edu; scheng~umn-cs.cs.umn.edu.

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

Fingerprint Dive into the research topics of 'Efficient distributed algorithms for single-source shortest paths and related problems on plane networks'. Together they form a unique fingerprint.

Cite this