The most vital edges in the minimum spanning tree problem
DOI10.1016/0020-0190(93)90247-7zbMATH Open0768.68051OpenAlexW1988871016WikidataQ127343631 ScholiaQ127343631MaRDI QIDQ1209313FDOQ1209313
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
Recommendations
- 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
- Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- Increasing the Weight of Minimum Spanning Trees
computational complexityminimum spanning treeweighted networkNP-hardbranch and bound algorithmmost vital edges
Trees (05C05) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Title not available (Why is that?)
- The k most vital arcs in the shortest path problem
- Finding the most vital arcs in a network
- Title not available (Why is that?)
- Removing Arcs from a Network
- Title not available (Why is that?)
- Finding the n Most Vital Links in Flow Networks
- Most vital links and nodes in weighted networks
- Multi-Terminal Network Flows
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- Determining the most vital link in a flow network
Cited In (18)
- Minimum cost edge blocker clique problem
- Title not available (Why is that?)
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
- Integer Programming Formulations for Minimum Spanning Tree Interdiction
- On recoverable and two-stage robust selection problems with budgeted uncertainty
- Increasing the Weight of Minimum Spanning Trees
- Exact algorithms for the minimum cost vertex blocker clique problem
- Connectivity interdiction
- Recoverable robust spanning tree problem under interval uncertainty representations
- Maximum Capacity Path Interdiction Problem with Fixed Costs
- Matching interdiction
- A survey on mixed-integer programming techniques in bilevel optimization
- The most vital edges with respect to the number of spanning trees in two- terminal series-parallel graphs
- On designing networks resilient to clique blockers
- Edge exchanges in the degree-constrained minimum spanning tree problem
- Parametric matroid interdiction
- Finding the most vital edge with respect to minimum spanning tree in weighted graphs
- Robust recoverable 0-1 optimization problems under polyhedral uncertainty
This page was built for publication: The most vital edges in the minimum spanning tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1209313)
