Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Finding 3-shredders efficiently
Hegde R. ACM Transactions on Algorithms2 (1):14-43,2006.Type:Article
Date Reviewed: Jun 20 2006

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)
Bookmark and Share
 
Trees (E.1 ... )
 
 
Computations On Discrete Structures (F.2.2 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Lists, Stacks, And Queues (E.1 ... )
 
 
Graph Theory (G.2.2 )
 
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Trees": Date
The hB-tree: a multiattribute indexing method with good guaranteed performance
Lomet D., Salzberg B. ACM Transactions on Database Systems 15(3): 625-658, 1990. Type: Article
Jun 1 1991
Multidimensional trees
Baldwin W., Strawn G. Theoretical Computer Science 84(2): 293-311, 1991. Type: Article
Oct 1 1992
Hash trees versus b-trees
Bell D., Deen S. The Computer Journal 27(3): 218-224, 1984. Type: Article
Feb 1 1985
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy