Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
From MaRDI portal
Publication:358656
DOI10.1007/s10878-011-9449-4zbMath1275.90113OpenAlexW2062808512MaRDI QIDQ358656
Daniel Vanderpooten, Sonia Toubaline, Cristina Bazgan
Publication date: 9 August 2013
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-011-9449-4
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (18)
Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases ⋮ Minimum edge blocker dominating set problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ Integer programming methods for solving binary interdiction games ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem ⋮ Bound and exact methods for assessing link vulnerability in complex networks ⋮ Shortest path interdiction problem with convex piecewise-linear costs ⋮ On designing networks resilient to clique blockers ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Parametric matroid interdiction ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Blockers for the stability number and the chromatic number ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
Cites Work
- Unnamed Item
- On the hardness of approximating minimum vertex cover
- 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
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- 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
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- Finding the n Most Vital Links in Flow Networks
- Efficient Algorithms for Finding the k Most Vital Edges for the Minimum Spanning Tree Problem
- Removing Arcs from a Network
- Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
This page was built for publication: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
