5
$\begingroup$

Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges.

Of course I could run a BFS for each vertex and for each edge to test if the remaining graph would be connected. But is there anything more efficient?

In the end I would like to uniformly draw a vertex/edge out of those that would not disconnect the graph, to make simulations for fail-over routing in a computer network.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

For vertices you could use articulation point algorithm that uses DFS and runs in $O(|V| + |E|)$ time. Similarly you could find bridges. Look here and here. But if there is no bridge and you are interested in cut-set (of edges) I guess you could use maximum flow minimum cut algorithm by assigning weight equal to 1 to each edge if they are not weighted. And finally if you are interested in subgraphs whose vertices are connected with each other (there is a path between each pair of vertices) then use an algorithm for computing strongly connected components.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks, articulation points and bridges are what I was looking for. The Boost Graph Library contains an implementation to find articulation points and biconneted components in $O(|V|+|E|)$. It can also be used to find brides: an edge is a bridge exactly if it is the only edge in a biconnected component. $\endgroup$
    – xblax
    Commented Jul 17, 2017 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.