A Simple Randomized 3-edge Connected Component Algorithm

Authors

  • Vladislav Haralampiev Faculty of Mathematics and Informatics, Sofia University "St. Kliment Ohridski", Bulgaria

DOI:

https://doi.org/10.55630/sjc.2018.12.265-280

Keywords:

Graph, Algorithm

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.

Downloads

Published

2019-01-23

Issue

Section

Articles