Network -> Regions -> Bicomponents

Contents - Index

NETWORK > REGIONS > BICOMPONENTS

PURPOSE Finds all the cutpoints or articulation points and bi-components or blocks of a graph.

DESCRIPTION A cutpoint of a graph is a vertex whose removal increases the number of components these are also called articulation points. A non-separable graph is a graph that is connected non-trivially and has no cutpoints. A block or bicomponent of a graph is a maximal non-separable subgraph. The name bi-component reflects the fact that it requires the deletion of two vertices to disconnect it. Bi-components overlap, but a vertex that is in more than one bi-component it must be a cutpoint.

PARAMETERS
Input dataset:
Name of file containing graph to be analyzed. Data type: Graph.

(output) block by actor matrix:(Default=BiComponents)
Name of file that will contain a block by actor incidence matrix. A 1 in column i row j means that node j is in bi-component i. This file is not displayed in the LOG FILE..

(output) cutpoint dataset:(Default=Cutpoints)
Name of file that contains a cutpoint indicator vector a 1 in row i indicates that i is a cutpoint.

LOG FILE Number of bi-components found.
List of bi-components, labeled - each bi-component is specified by the vertices it contains.
Cutpoint indicator vector

TIMING O(N^2).

COMMENTS None.

REFERENCES None.