Efficient algorithms for finding the most vital edge of a minimum spanning tree

DOI10.1016/0020-0190(93)90082-KzbMath0942.68579OpenAlexW2069416867MaRDI QIDQ1313724

Naoki Katoh, Kazuo Iwano

Publication date: 14 August 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90082-k

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (12)

A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges ⋮ Critical edges/nodes for the minimum spanning tree problem: complexity and approximation ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ Parametric matroid interdiction ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ NC algorithms for the Single Most Vital Edge problem with respect to shortest paths ⋮ The swap edges of a multiple-sources routing tree ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm ⋮ Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\) ⋮ Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗

Cites Work

• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Applications of Path Compression on Balanced Trees
• Fibonacci heaps and their uses in improved network optimization algorithms

This page was built for publication: Efficient algorithms for finding the most vital edge of a minimum spanning tree