3
$\begingroup$

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)?

  • 0
    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.2011-03-22

0 Answers 0