The most vital edges in the minimum spanning tree problem
From MaRDI portal
Publication:1209313
DOI10.1016/0020-0190(93)90247-7zbMath0768.68051WikidataQ127343631 ScholiaQ127343631MaRDI QIDQ1209313
Kao-Chêng Lin, Maw-Sheng Chern
Publication date: 16 May 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(93)90247-7
computational complexity; NP-hard; branch and bound algorithm; minimum spanning tree; weighted network; most vital edges
68Q25: Analysis of algorithms and problem complexity
05C05: Trees
68R10: Graph theory (including graph drawing) in computer science
Related Items
Integer Programming Formulations for Minimum Spanning Tree Interdiction, A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games, Maximum Capacity Path Interdiction Problem with Fixed Costs, On designing networks resilient to clique blockers, A survey on mixed-integer programming techniques in bilevel optimization, Matching interdiction, Minimum cost edge blocker clique problem, Exact algorithms for the minimum cost vertex blocker clique problem, On recoverable and two-stage robust selection problems with budgeted uncertainty, Connectivity interdiction, Recoverable robust spanning tree problem under interval uncertainty representations, Robust recoverable 0-1 optimization problems under polyhedral uncertainty
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The k most vital arcs in the shortest path problem
- Most vital links and nodes in weighted networks
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- Finding the most vital arcs in a network
- Multi-Terminal Network Flows
- Finding the n Most Vital Links in Flow Networks
- Removing Arcs from a Network
- Determining the most vital link in a flow network