An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem 


Vol. 7,  No. 5, pp. 1370-1376, May  2000
10.3745/KIPSTE.2000.7.5.1370


PDF
  Abstract

Consider the problem to update Breadth-First Spanning Tree in response to topology change of the network. This paper proposes an efficient distributed algorithm that solves such a problem after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are Ο(p√q q a n') respectively, where n' is the number of processors in the network after the topology change, a is the number of added links, p is the total number of links in the biconnected component (of the network before the topology change) including the deleted links or added links, and q is the total number of processors in the biconnected component including the deleted links or added links.

  Statistics
  Cite this article

[IEEE Style]

J. H. Park, Y. Y. Park, S. H. Hwang, "An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 7, no. 5, pp. 1370-1376, 2000. DOI: 10.3745/KIPSTE.2000.7.5.1370.

[ACM Style]

Jung Ho Park, Yoon Young Park, and Suk Hyung Hwang. 2000. An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 5, (2000), 1370-1376. DOI: 10.3745/KIPSTE.2000.7.5.1370.

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