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
Articulation Point in directed graph.
Moderator: Board moderators

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 Contact:
Articulation Point in directed graph.
You should not always say what you know, but you should always know what you say.
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.
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
HomePage

 Experienced poster
 Posts: 110
 Joined: Tue May 06, 2008 2:18 pm
 Location: CSEDU, Bangladesh
 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,
So, 4 is not such a point.
Code: Select all
1>2
 
 
\/ \/
3>4
You should not always say what you know, but you should always know what you say.