Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
From MaRDI portal
Publication:358656
DOI10.1007/S10878-011-9449-4zbMATH Open1275.90113OpenAlexW2062808512MaRDI QIDQ358656FDOQ358656
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)
Cites Work
- Title not available (Why is that?)
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the hardness of approximating minimum vertex cover
- Deterministic network interdiction
- Removing Arcs from a Network
- Finding the n Most Vital Links in Flow Networks
- Complexity of Determining the Most Vital Elements for the 1-median and 1-center Location Problems
- On short paths interdiction problems: Total and node-wise limited interdiction
- A faster computation of the most vital edge of a shortest path
- 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
- Finding the \(k\) most vital edges with respect to minimum spanning tree
- 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 trees for fixed \(k\)
Cited In (25)
- Approximating minimum-cost graph problems with spanning tree edges
- Minimum cost edge blocker clique problem
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- Increasing the Weight of Minimum Spanning Trees
- Title not available (Why is that?)
- Exact algorithms for the minimum cost vertex blocker clique problem
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- 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
- Minimum edge blocker dominating set problem
- Blockers for the stability number and the chromatic number
- Bound and exact methods for assessing link vulnerability in complex networks
- The most vital edges in the minimum spanning tree problem
- A survey on mixed-integer programming techniques in bilevel optimization
- Integer programming methods for solving binary interdiction games
- A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths
- Critical edges for the assignment problem: complexity and exact resolution
- Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
- On minimum leaf spanning trees and a criticality notion
- Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut
- On designing networks resilient to clique blockers
- Shortest path interdiction problem with convex piecewise-linear costs
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Parametric matroid interdiction
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)
