Biconnected component

A biconnected component is a maximal connected subgraph of a graph in which any two nodes have at least two totally different paths between them. A graph is considered biconnected if and only if its unique biconnected component is itself. The process of finding biconnected components can be sparsified by replacing each biconnected component with a cycle that contains the vertices in the component, resulting in a smaller graph that still contains the necessary information for computing the biconnected components of the original graph.From: Discrete Mathematics [2019], TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration [2022], Digital Systems and Applications [2019]

Graph Algorithms I

View Chapter

Purchase Book

Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019

R. Balakrishnan, Sriraman Sridharan

A connected graph with at least two vertices is a biconnected graphbiconnected graph or a blockblock if it does not contain a cut vertex. A biconnected componentbiconnected component or blockblock of a connected graph is a maximal induced subgraph without any cut vertex. In other words, the graph H is a biconnected component of the graph G if H is biconnected in its own right and for any vertex x lying outside of H, the subgraph of G induced by the vertices of H∪x is either disconnected or contains a cut vertex.

Fast data acquisition algorithm for remote monitoring system of smart home

View Article

Journal Information

Published in International Journal of Computers and Applications, 2022

Jie Zhang, Haibo Pu

The initialization set , , and are empty. is the joint point set; is the set of nodes of the biconnected component, , and of which is the number of the double connected components in the domain; is the edge set of the biconnected component.

Biconnected component

Explore chapters and articles related to this topic

Graph Algorithms I

Fast data acquisition algorithm for remote monitoring system of smart home