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.90370OpenAlexW2092574579MaRDI 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
Programming involving graphs or networks (90C35) Trees (05C05) Mixed integer programming (90C11) Deterministic network models in operations research (90B10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
Minimum edge blocker dominating set problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Parametric matroid interdiction ⋮ An accelerating algorithm for maximum shortest path interdiction problem by upgrading edges on trees under unit Hamming distance ⋮ Robust capacitated Steiner trees and networks with uniform demands ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ A dynamic reformulation heuristic for generalized interdiction problems ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm
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\)
This page was built for publication: Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
