Critical edges/ vertices in directed graph
Difference between en1 and en2, changed 9 character(s)
Given a weighted directed graph $G$ and $2$ different vertices $s$ and $t$ in it. How can we find all edges $e$ such  that removing $e$ increases the distance between $s$ and $t$? Is there a better way then $O(E*(E + V))$ where we test each edge by removing it? Can we also find all vertices $v$ defined analogously?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English frying_pan 2023-07-21 15:46:56 21 Tiny change: 'then $O(E*(E + V))$ where' -> 'then $O(E*E*log(V))$ where'
en2 English frying_pan 2023-07-21 15:45:32 9 Tiny change: 'Given a directed ' -> 'Given a weighted directed '
en1 English frying_pan 2023-07-21 15:44:20 349 Initial revision (published)