Improvement on The Complexity of Distributed Depth First Search Protocol


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 3, No. 4, pp. 926-937, Jul. 1996
10.3745/KIPSTE.1996.3.4.926,   PDF Download:

Abstract

A graph traversal technique is a certain pattern of ''visiting'' nodes of a graph. Many special traversal techniques have been applied to solve graph related problems. For example, the depth first search technique has been used for finding strongly connected components of a directed graph or biconnected components of a general graph. The distributed protocol to implement this depth first search technique of the distributed network can be divided into a fixed topology problem where there is no topological change and a dynamic topology problem which has some topological changes. Therefore, in this paper, we present a more efficient distributed depth first search protocol with fixed topology and s resilient distributed depth first search protocol where there are topological changes for the distributed network. Also, we analysed the message and time complexity of the presented protocols and showed the improved results than the complexities of the other distributed depth first search protocols.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
C. J. Won, "Improvement on The Complexity of Distributed Depth First Search Protocol," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 3, no. 4, pp. 926-937, 1996. DOI: 10.3745/KIPSTE.1996.3.4.926.

[ACM Style]
Choe Jong Won. 1996. Improvement on The Complexity of Distributed Depth First Search Protocol. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 3, 4, (1996), 926-937. DOI: 10.3745/KIPSTE.1996.3.4.926.