Sunday, 15 April 2007

algorithms - Effect on connectivity when partitioning a graph

I have a connected graph G=(V,E)G=(V,E), VV being the vertex set and EE being the edge set. I partition the graph into components C=C1,dots,CnC=C1,dots,Cn such that all CiCi are pairwise disjoint.



Take two vertices s,tinVs,tinV such that s,ts,t are connected by a path. Is there an O(|V|+|E|)O(|V|+|E|) algorithm to find out the list of all CiinCCiinC such that if we remove the vertices in CiCi from the graph, then ss will become disconnected from tt.



I know there is the O(|C|(|V|+|E|))O(|C|(|V|+|E|)) algorithm to do so by removing vertices in CiinCCiinC from the graph for all 1leqileqn1leqileqn and then checking if ss and tt are connected.
This can be somewhat improved if we take all edge weights as 1 and compute the shortest path and then consider only components whose vertices are present in the shortest path but this still has worst case complexity O(|C|(|V|+|E|))O(|C|(|V|+|E|)).

No comments:

Post a Comment