mockers
Would you like to react to this message? Create an account in a few clicks or log in to continue.

articulation vertex

Go down

articulation vertex Empty articulation vertex

Post  shivang Wed Feb 25, 2009 6:50 pm

An articulation vertex of a graph G is a vertex whose deletion disconnects G . Let G be a graph with n vertices and m edges. Give a simple O(n+m) algorithm for finding a vertex of G that is not an articulation vertex i.e. whose deletion does not disconnects G.

Q-> Following up on the previous problem, give a O(n+m) algorithm that finds a deletion order for the n vertices such that no deletion disconnects the graph
shivang
shivang

Posts : 42
Join date : 2009-01-30
Age : 35

Back to top Go down

Back to top


 
Permissions in this forum:
You cannot reply to topics in this forum