Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6037
Title: Dividing a Graph into Triconnected Components
Authors: Hopcroft, John E.
Tarjan, Robert Endre
Keywords: computer science
technical report
Issue Date: Feb-1974
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR74-197
Abstract: An algorithm for dividing a graph into triconnected components is presented. When implemented on a random access computer, the algorithm requires $O(V+E)$ time and space to analyze a graph with $V$ vertices and $E$ edges. The algorithms is both theoretically optimal to within a constant factor and efficient in practice. Keywords: articulation point, connectivity, depth-first search, graph, separability, separation, triconnectivity.
URI: http://hdl.handle.net/1813/6037
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
74-197.pdf1.64 MBAdobe PDFView/Open
74-197.ps505.03 kBPostscriptView/Open

Refworks Export

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

 

© 2014 Cornell University Library Contact Us