## Articulation Point in directed graph.

Moderator: Board moderators

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Articulation Point in directed graph.

Which algorithm do I need to follow if I want to find all the articulation point on a given directed graph, can anyone please provide me with some papers, hints, abstracts, or implementations? Thanks in advance.

zobayer1[at]gmail[dot]com
You should not always say what you know, but you should always know what you say.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: Articulation Point in directed graph.

Can you elaborate a bit? What is the definition of articulation points for directed graph?

Say a graph is

1 -> 2
2 -> 3
3 -> 4
4 -> 1

Since if any node is removed, the connectivity gets changed. For example, if 1 is removed we can't go from 4 to 2.

So, according to your definition all the nodes are articulation points. Am I right?

Cause the formal definition is, articulation point is a node, if its removed, the graph is separated into two or more parts. According to this definition whether the graph is directed or undirected the result is same.
Ami ekhono shopno dekhi...
HomePage

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: Articulation Point in directed graph.

Yes, definitely you are right, except for node 4, here is another example, lets look at this graph,

Code: Select all

``````              1------------------>2
|                   |
|                   |
\/                 \/
3------------------>4
``````
So, 4 is not such a point.
You should not always say what you know, but you should always know what you say.