0
$\begingroup$

If we have a connected undirected graph $G = (V,E)$, we want to find an algorithm($O(|V|+|E|)$ that finds if there is such an edge $e\in E$ that $G$ will remain connected after its deletion.

Also is there a way to speed up to $O(|V|)$?

  • 0
    What is a "coherent" graph? Google doesn't seem to find anything relevant? Do you mean "connected"?2011-12-31
  • 0
    Yes it is connected. I hate these names cause I always forget them.2011-12-31
  • 0
    Could this help: [Design an algorithm to check if a given graph is connected](http://wiki.answers.com/Q/Design_an_algorithm_to_check_if_a_given_graph_is_connected)?2012-04-05

1 Answers 1