Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem 


Vol. 1,  No. 2, pp. 184-193, Jul.  1994
10.3745/KIPSTE.1994.1.2.184


PDF
  Abstract

This paper considers the Updating Minimum-weight Spanning Tree Problem(UMP), that is, the problem to update the Minimum-weight Spanning Tree(MST) in response to topology change of the network. This paper proposes the algorithm which reconstructs the MST after several links deleted and added. Its message complexity and its ideal-time complexity are O(m n log(t f)) and O(n n log(t f)) respectively, where n is the number of processors in the network, t(resp. f) is the number of added links (resp. the number of deleted links of the old MST), and m=t n if f=0, m=e (i.e. the number of links in the network after the topology change) otherwise. Moreover the last part of this paper touches on the algorithm which deals with deletion and addition of processors as well as links.

  Statistics
  Cite this article

[IEEE Style]

P. J. Ho and M. J. Young, "Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 1, no. 2, pp. 184-193, 1994. DOI: 10.3745/KIPSTE.1994.1.2.184.

[ACM Style]

Park Jung Ho and Min Joon Young. 1994. Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 1, 2, (1994), 184-193. DOI: 10.3745/KIPSTE.1994.1.2.184.

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