Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem 


Vol. 5,  No. 10, pp. 2512-2520, Oct.  1998
10.3745/KIPSTE.1998.5.10.2512


PDF
  Abstract

This paper considers the Biconnected-components Reconstruction Problem(BRP), that is, the problem to reconstruct the biconnected-components in response to topology change of the network. This paper proposes a distributed algorithm that solves the BRP after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are O(n' a b) and O(n') respectively, where n' is the number of processors in the network after the topology change, a is the number of added links, and b is the total number of links in the biconnected components (of the network before the topology change) including the deleted links.

  Statistics
  Cite this article

[IEEE Style]

L. C. Suk, P. J. Ho, K. Y. Seol, "Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 10, pp. 2512-2520, 1998. DOI: 10.3745/KIPSTE.1998.5.10.2512.

[ACM Style]

Lee Chang Suk, Park Jung Ho, and Koo Yeon Seol. 1998. Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 10, (1998), 2512-2520. DOI: 10.3745/KIPSTE.1998.5.10.2512.

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