A Distributed Algorithm for Weighted Shortest Path Problem 


Vol. 6,  No. 1, pp. 42-48, Jan.  1999
10.3745/KIPSTE.1999.6.1.42


PDF
  Abstract

Consider the situation that informations necessary to solve a certain problem are distributed among processors on a network. It is called a distributed algorithm that in this situation each processor exchanges the message with adjacent processors to solve the problem. This paper proposes a distributed algorithm to solve the problem that constructs the weighted shortest path tree in an asynchronous network system. In general, a distributed algorithm is estimated by the number of messages(message complexity) and the number of unit complexity(ideal time complexity). Message complexity and ideal-time complexity of the distributed algorithm proposed in this paper are O(n5/3) and O(n%u221An) respectively, where n is the number of processors on the network.

  Statistics
  Cite this article

[IEEE Style]

P. J. Ho and P. Y. Young, "A Distributed Algorithm for Weighted Shortest Path Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 1, pp. 42-48, 1999. DOI: 10.3745/KIPSTE.1999.6.1.42.

[ACM Style]

Park Jung Ho and Park Yoon Young. 1999. A Distributed Algorithm for Weighted Shortest Path Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 1, (1999), 42-48. DOI: 10.3745/KIPSTE.1999.6.1.42.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals