3
$\begingroup$

What word is most commonly used in graph theory for edges which, when removed from a graph, increase the number of connected components?

Such edges can be found in polynomial time. Where was such an algorithm proposed originally? Are there different algorithms?

$\endgroup$
6
$\begingroup$

They're called bridges. According to Wikipedia,

A linear time algorithm for finding the bridges in a graph was described by Robert Tarjan in 1974.

$\endgroup$
2
  • 2
    $\begingroup$ As noted in the Wikipedia article, they may also be called "cut-edges". $\endgroup$ Apr 24 '13 at 18:52
  • 1
    $\begingroup$ In the context of planarity, the term bridge has another meaning, so cut-edge is safer. $\endgroup$ Apr 24 '13 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.