๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Stabilizing Algorithm for Finding Biconnected Components

โœ Scribed by Mehmet Hakan Karaata

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
209 KB
Volume
62
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

In this paper, a self-stabilizing algorithm is presented for finding biconnected components of a connected undirected graph on a distributed or network model of computation. The algorithm is resilient to transient faults, therefore, it does not require initialization. The proposed algorithm is based on stabilizing BFS construction and bridge-finding algorithms. Upon termination of these algorithms, the proposed algorithm terminates after Oรฐdรž rounds, where d is the diameter of the biconnected component with the largest diameter in the graph. The paper concludes with remarks on issues such as the adaptiveness of the algorithm.

๐Ÿ“œ SIMILAR VOLUMES

Finding biconnected components in O(n) t
Finding biconnected components in O(n) time for a class of graphs
โœ Y.Daniel Liang; Chongkye Rhee ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 460 KB

A rooted tree is called a single-branch tree if there. is exactly one nonleaf vertex on each level except the bottom level of the tree. We present an O(n) time algorithm for finding biconnected components in a graph G, assuming that a single-branch breadth-first search (SBS) tree of any connected in

Sub-linear Distributed Algorithms for Sp
Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
โœ Ramakrishna Thurimella ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 295 KB

A certificate for the k connectivity k connectivity refers to both k-edge . connectivity and k-vertex connectivity unless explicitly stated otherwise of a graph ลฝ . O kn . We present a distributed algorithm for computing a sparse certificate for k ลฝ . ลฝ . connectivity. Let f n and g n be the distri

A self-stabilizing algorithm for finding
A self-stabilizing algorithm for finding a minimal 2-dominating set assuming the distributed demon model
โœ Tetz C. Huang; Ji-Cherng Lin; Chih-Yuan Chen; Cheng-Pin Wang ๐Ÿ“‚ Article ๐Ÿ“… 2007 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 202 KB

A 2-dominating set in a distributed system is a set of processors such that each processor outside the set has at least two neighbors in the set. In applications, a 2-dominating set can be considered as an ideal place in the system for allocating resources, and a minimal 2-dominating set allows for