Articulation Point in directed graph.

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Articulation Point in directed graph.

Post by zobayer » Mon Jul 12, 2010 10:14 pm

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. :D

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
Location: Dhaka, Bangladesh
Contact:

Re: Articulation Point in directed graph.

Post by Jan » Wed Jul 14, 2010 12:49 pm

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
Location: CSE-DU, Bangladesh
Contact:

Re: Articulation Point in directed graph.

Post by zobayer » Sat Jul 31, 2010 8:47 pm

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.

Post Reply

Return to “Algorithms”