Finding vertices in a graph whose removal disconnects the graph into three or more components

Revision en1, by bigintegers, 2020-02-28 17:01:00

Recently, I learned about Tarjan and Kosaraju's algorithms to find articulation points.

However, I was wondering whether there are algorithms to find vertices whose removal disconnects the graph into three or more components (as opposed to two). I've searched online, and I cannot find anything (perhaps I'm using the wrong search terms?).

I have a guess, but I'm not sure if this is correct. I think that we can take the DFS tree, and conclude that a vertex satisfies my condition if one of the following is true:

1) It's the parent of the DFS tree with three or more children.

2) It's not the parent of the DFS tree with two children.

This seems too easy to me, so I'm pretty sure it's wrong.

Can someone please help me with this problem?

Tags #graph theory, #graph, articulation point, #dfs, #dfs and similar

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English bigintegers 2020-02-28 17:01:00 853 Initial revision (published)