## Abstract

For a connected, undirected and weighted graph G = (V, E), the problem of finding the k most vital edges of G with respect to minimum spanning tree is to find k edges in G whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary k. In this paper, we first describe a simple exact algorithm for this problem, based on the approach of edge replacement in the minimum spanning tree of G. Next we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For |V| = n and |E| = m, our algorithm producing optimal solution has a time complexity of O(mn) with probability of success at least e ^{-}k ^{2}/2(m-n-1)-2 log _{c} ^{k}/k-4, c = 1+1/2 ^{k/2}, and the algorithm producing approximate solution runs in time O(mn+nk ^{2} log k) and yields results within factor 2 to the optimal one. Finally we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in O(n) time using n ^{2} processors, and the second algorithm runs in O(log ^{2} n) time using mn/log n processors.

Original language | English |
---|---|

Pages | 255-262 |

Number of pages | 8 |

Publication status | Published - 1997 |

Externally published | Yes |

Event | Proceedings of the 1997 IEEE National Aerospace and Electronics Conference, NAECON. Part 1 (of 2) - Dayton, OH, USA Duration: 14 Jul 1997 → 17 Jul 1997 |

### Conference

Conference | Proceedings of the 1997 IEEE National Aerospace and Electronics Conference, NAECON. Part 1 (of 2) |
---|---|

City | Dayton, OH, USA |

Period | 14/07/97 → 17/07/97 |