Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation:
Serdica Journal of Computing, Vol. 12, No 4, (2018), 265p-280p
Abstract:
Finding the 3-edge connected components of a graph is a well-researched
problem for which many algorithms are known. In this paper, we present a new
linear-time randomized algorithm for the problem. To the best of our knowledge,
this is the first randomized algorithm for partitioning a graph into 3-edge connected
components. The algorithm is a composition of simple building blocks, it is easy to
understand and implement, and it has no corner cases.
