Computing Reviews

Finding 3-shredders efficiently
Hegde R. ACM Transactions on Algorithms2(1):14-43,2006.Type:Article
Date Reviewed: 06/20/06

A k-shredder in an undirected graph is a vertex cut of size k whose removal results in at least three components. The author presents a linear algorithm to find the set of 3-shredders in a 3-connected graph. The algorithm is quite involved and consists of four stages that are described meticulously by the author. First, the graph is tested for 3-connectivity with the Hopcroft-Tarjan algorithm. Next, a set of triples of vertices is generated that includes all of the 3-shredders. Then, multiple copies of triples are eliminated. Finally, triples that are not 3-shredders are identified and discarded by detecting those that have edges between vertices of the three potential components. Several possible cases in the last stage are presented in detail.

Reviewer:  Adam Drozdek Review #: CR132937 (0704-0376)

Reproduction in whole or in part without permission is prohibited.   Copyright 2024 ComputingReviews.com™
Terms of Use
| Privacy Policy