Critical edges/ vertices in directed graph

Правка en2, от frying_pan, 2023-07-21 15:45:32

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский 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 Английский frying_pan 2023-07-21 15:45:32 9 Tiny change: 'Given a directed ' -> 'Given a weighted directed '
en1 Английский frying_pan 2023-07-21 15:44:20 349 Initial revision (published)