Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
From MaRDI portal
Publication:1761238
DOI10.1016/j.cor.2012.02.023zbMath1251.90370MaRDI QIDQ1761238
Cristina Bazgan, Daniel Vanderpooten, Sonia Toubaline
Publication date: 15 November 2012
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2012.02.023
90C35: Programming involving graphs or networks
05C05: Trees
90C11: Mixed integer programming
90B10: Deterministic network models in operations research
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths, Integer Programming Formulations for Minimum Spanning Tree Interdiction, Parametric matroid interdiction, Robust capacitated Steiner trees and networks with uniform demands, Minimum edge blocker dominating set problem, A dynamic reformulation heuristic for generalized interdiction problems, Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm, Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance, Critical edges for the assignment problem: complexity and exact resolution, An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance, A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
Cites Work
- Unnamed Item
- Unnamed Item
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- On short paths interdiction problems: Total and node-wise limited interdiction
- Finding the k most vital edges in the minimum spanning tree problem
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- Efficient algorithms for finding the most vital edge of a minimum spanning tree
- A faster computation of the most vital edge of a shortest path
- Deterministic network interdiction
- Finding the \(k\) most vital edges with respect to minimum spanning tree
- Applications of Path Compression on Balanced Trees
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- An optimal minimum spanning tree algorithm
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
- Finding the n Most Vital Links in Flow Networks
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Removing Arcs from a Network
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
- Algorithms and Computation
- Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
