CODEWITHSUNDEEP
algorithmgraphvertex
pfinferno
pfinferno

Reputation: 1945

Finding a vertex whose removal will disconnect two others

I'm trying to make an algorithm that runs in O(V + E) time for an undirected graph G = (V, E) that, given two vertices a and b, finds a vertex c whose removal will cause a and b to be disconnected from each other. As a part of this, I'm trying to argue that if the shortest path from a to b has length greater than V/2, then G must have a 'c' for a and b.

I can see visually, looking at a graph, why the length from a to b if greater than v/2 has to have a choke point for a and b. I guess the reason would be because if the length was less than or equal to v/2, than there's a chance a and b could be connected to each other without another vertex in between?

For the algorithm, I thought about using Dijkstra's algorithm to find the shortest path between a and b, and then pick a vertex along that path and remove it and check if the path is the same. Is this the way to go about it or is there a better way?

Upvotes: 2

Views: 1606

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Because the graph is undirected so, vertex c exists if and only if c is a brigde, which means, for all paths from a to b and vice versa, they all have to go through c,

So you don't need to use Dijkstra, just use a simple Breadth First Search, and try all vertices on the path found by BFS, if its removal causes a and b disconnected, it will be c.

Upvotes: 1

Related Questions