BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2018 >
Volume 12, Number 4 >

Please use this identifier to cite or link to this item:

Title: A Simple Randomized 3-edge Connected Component Algorithm
Authors: Haralampiev, Vladislav
Keywords: Graph
Issue Date: 2018
Publisher: 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.
ISSN: 1312-6555
Appears in Collections:Volume 12, Number 4

Files in This Item:

File Description SizeFormat
sjc-vol12-num4-2018-p265-p280.pdf437.04 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License