Live briefing
Everything about Biconnected component
Maximal biconnected subgraph
In graph theory, a biconnected component or block is a maximal biconnected subgraph. Any connected graph decomposes into a tree of biconnected components called the block-cut tree of the graph. The blocks are attached to each other at shared vertices called cut vertices or separating vertices or articulation points. Specifically, a cut vertex is any vertex whose removal increases the number of connected components. A block containing at most one cut vertex is called a leaf block, it corresponds to a leaf vertex in the block-cut tree. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Biconnected componentA 5-minute orientation
- Skim a recent paper: Two-Hop Biconnected Components in the Global Liner Shipping Network Reveal International Trade StatusesInfluential work since 2022
- Pick up a classic book: Discrete and combinatorial mathematicsThe most-reprinted book on the subject
- Read the landmark paper: Maintaining bridge-connected and biconnected components on-lineCited 83 times
- Go sideways: Bipolar orientationA closely related topic
- Go sideways: Bridge (graph theory)A closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Maintaining bridge-connected and biconnected components on-line
How to find biconnected components in distributed networks
Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
Large-deviation properties of the largest biconnected component for random graphs
Smashing Peacocks Further: Drawing Quasi-Trees from Biconnected Components
A Stabilizing Algorithm for Finding Biconnected Components
Efficient Multicore Algorithms For Identifying Biconnected Components
Why should biconnected components be identified first
🆕 Influential since 2022
📚 Books worth reading
Discrete and combinatorial mathematicsRalph P. Grimaldi · 1985
Data structures and algorithm analysis in CMark Allen Weiss · 1993
Data structures & algorithm analysis in JavaMark Allen Weiss · 1999
Fundamentals of data structures in CEllis Horowitz · 1993
Computer algorithmsEllis Horowitz · 1997
Fundamentals of computer algorithmsEllis Horowitz · 1978
Algorithm Design and ApplicationsMichael T. Goodrich, Roberto Tamassia · 2014
প্রোগ্রামিং কনটেস্টমোঃ মাহবুবুল হাসান · 2016
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Bipolar orientation In graph theory, a bipolar orientation or st-orientation of an undirected graph is an assignment of a direction to each edge (an orientation) that causes…
- Bridge (graph theory) In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently…
- Block graph In graph theory, a branch of combinatorial mathematics, a block graph or clique tree is a type of undirected graph in which every biconnected component…
- SPQR tree In graph theory, a branch of mathematics, the triconnected components of a biconnected graph are a system of smaller graphs that describe all of the 2-vertex…
- Strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly…
- Path-based strong component algorithm In graph theory, the strongly connected components of a directed graph may be found using an algorithm that uses depth-first search in combination with…
- Component (graph theory) In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph…
- Biconnected graph In graph theory, a biconnected graph is a connected and "nonseparable" graph, meaning that if any one vertex were to be removed, the graph will remain…