Biconnected components: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Basic definitions ==
# [[Basic graph definitions]]
== Input ==
== Input ==


A [[Basic graph definitions|connected]] [[Basic graph definitions|undirected graph]] <math>G=(V,E)</math>.
An [[Basic graph definitions|undirected graph]] <math>G=(V,E)</math>, which must be [[Basic graph definitions#Connectedness|connected]]. For ease of notation and without loss of generality, we assume that <math>G</math> is [[Basic graph definitions|simple]].


== Output ==
== Output ==

Latest revision as of 19:07, 9 November 2014

Basic definitions

  1. Basic graph definitions

Input

An undirected graph [math]\displaystyle{ G=(V,E) }[/math], which must be connected. For ease of notation and without loss of generality, we assume that [math]\displaystyle{ G }[/math] is simple.

Output

A set of sets of nodes such that each set of nodes is exactly one biconnected component.

Known algorithms

  1. Hopcroft-Tarjan