Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If I have a biconnected graph and I remove a vertex (without forgetting which vertex was removed and which vertices it was adjacent to), is there an way to check the biconnectivity of the resulting graph that is easier than checking the biconnectivity of an arbitrary graph? E.g., is there a method that in the best case requires only local examination (perhaps some property of the adjacent vertices)?

share|improve this question
    
I don't think there can be a purely local algorithm; consider a graph which is basically two separate graphs, connected with two widely-separated bridges. Removing a node to destroy one of the bridges doesn't give any obvious way to find that there's only one other bridge at the far end of the graph. That said, there are clearly some shortcuts. For example, if the subgraph consisting only of the removed node's neighbors is still 2-connected, then the entire graph is as well. –  Paul Z Mar 21 '11 at 19:23
    
That shortcut you mentioned is exactly the sort of thing I'm after. I do realize that no algorithm could be local in the worst case. –  user8531 Mar 22 '11 at 19:33

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.