Edit page

Articulation points

A vertex in an undirected connected graph is an articulation point (or cut vertex) if removing it (and edges through it) disconnects the graph. Articulation points represent vulnerabilities in a connected network – single points whose failure would split the network into 2 or more components. They are useful for designing reliable networks. For a disconnected undirected graph, an articulation point is a vertex removing which increases number of connected components. [Source: Geeksforgeeks]

Complexity

NameBest timeComments
Articulation pointsv + eBased on the algorithm used.

* Where v = number of vertices; e = number of edges

References

  • Geeksforgeeks
  • Wikipedia
  • YouTube
  • Hackerearth
  • cp-algorithms