Abstract
Let G(V, E, w) be an undirected, weighted, connected simple graph. Let P be a minimization problem in G. Edge e*∈E is called the most vital edge if its removal from G maximizes the value of P in G(V, E-{e*}, w). This paper considers the most vital edge with respect to the minimum spanning tree problem and the single-source shortest path problem. An O(n) optimal algorithm for finding the most vital edge with respect to these two problems on an n×n mesh array is presented. The algorithm is simulated on an n×n×n hypercube array, and an O(log2 n) time algorithm is then obtained, which is faster than a previously known result on the same model.
Original language | English |
---|---|
Pages (from-to) | 197-205 |
Number of pages | 9 |
Journal | International Journal of Parallel and Distributed Systems and Networks |
Volume | 3 |
Issue number | 4 |
Publication status | Published - 2000 |