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

Правка en1, от 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?

Теги #graph theory, #graph, articulation point, #dfs, #dfs and similar

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский bigintegers 2020-02-28 17:01:00 853 Initial revision (published)