The most vital edges in the minimum spanning tree problem

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

zbMATH Keywords

computational complexity; NP-hard; branch and bound algorithm; minimum spanning tree; weighted network; most vital edges

Mathematics Subject Classification ID

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