Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
From MaRDI portal
Recommendations
- The most vital edges in the minimum spanning tree problem
- Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
- Efficient algorithms for finding the \(k\) most vital edges for the minimum spanning tree problem
- Finding the \(k\) most vital edges with respect to minimum spanning tree
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
Cites work
- scientific article; zbMATH DE number 871953 (Why is no real title available?)
- A faster computation of the most vital edge of a shortest path
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- Deterministic network interdiction
- Efficient algorithms for finding the \(k\) most vital edges for the minimum spanning tree problem
- Efficient algorithms for finding the most vital edge of a minimum spanning tree
- Finding the n Most Vital Links in Flow Networks
- Finding the \(k\) most vital edges with respect to minimum spanning tree
- Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
- 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
- On short paths interdiction problems: Total and node-wise limited interdiction
- On the hardness of approximating minimum vertex cover
- Removing Arcs from a Network
Cited in
(30)- Exact algorithms for the minimum cost vertex blocker clique problem
- Blockers for the stability number and the chromatic number
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- On the complexity of the bilevel minimum spanning tree problem
- Shortest path interdiction problem with convex piecewise-linear costs
- Increasing the Weight of Minimum Spanning Trees
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
- Approximating minimum-cost graph problems with spanning tree edges
- Complexity of most vital nodes for independent set in graphs related to tree structures
- Minimum cost edge blocker clique problem
- Critical edges for the assignment problem: complexity and exact resolution
- Bound and exact methods for assessing link vulnerability in complex networks
- Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
- Improved Algorithms for MST and Metric-TSP Interdiction
- Complexity of determining the most vital elements for the \(p\)-median and \(p\)-center location problems
- A refined complexity analysis of finding the most vital edges for undirected shortest paths
- A survey on mixed-integer programming techniques in bilevel optimization
- On designing networks resilient to clique blockers
- The most vital edges in the minimum spanning tree problem
- Minimum edge blocker dominating set problem
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- scientific article; zbMATH DE number 3956440 (Why is no real title available?)
- Integer programming methods for solving binary interdiction games
- Exact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problem
- Parametric matroid interdiction
- The minimum spanning tree problem with non-terminal set
- A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
- On minimum leaf spanning trees and a criticality notion
This page was built for publication: Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q358656)
