Finding the Triconnected Components of a Graph

Abstract

An algorithm for decomposing a graph into triconnected components is presented. The algorithm requires 0(V + E) time and space when implemented on a random access computer, where V is the number of vertices and E is the number of edges in the graph. The algorithm is both theoretically optimal (to within a constant factor) and efficient in practice.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1972
Accession Number
AD0746856

Entities

People

  • John E. Hopcroft
  • Robert Tarjan

Organizations

  • Cornell University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Graph Theory
  • Military Research
  • New York
  • Polygons
  • Sequences
  • Splitting
  • Triangles
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space