The most vital edges in the minimum spanning tree problem

DOI10.1016/0020-0190(93)90247-7zbMath0768.68051OpenAlexW1988871016WikidataQ127343631 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 complexityNP-hardbranch and bound algorithmminimum spanning treeweighted networkmost vital edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Minimum cost edge blocker clique problem ⋮ Exact algorithms for the minimum cost vertex blocker clique problem ⋮ Integer Programming Formulations for Minimum Spanning Tree Interdiction ⋮ A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games ⋮ Matching interdiction ⋮ Recoverable robust spanning tree problem under interval uncertainty representations ⋮ On recoverable and two-stage robust selection problems with budgeted uncertainty ⋮ On designing networks resilient to clique blockers ⋮ A survey on mixed-integer programming techniques in bilevel optimization ⋮ Parametric matroid interdiction ⋮ Robust recoverable 0-1 optimization problems under polyhedral uncertainty ⋮ Maximum Capacity Path Interdiction Problem with Fixed Costs ⋮ Connectivity interdiction

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The most vital edges in the minimum spanning tree problem