The most vital edges in the minimum spanning tree problem

DOI10.1016/0020-0190(93)90247-7MaRDI QIDQ1209313zbMATH OpenOpenAlexWikidataFDO

Authors 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 complexityminimum spanning treeweighted networkNP-hardbranch and bound algorithmmost vital edges

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Determining the most vital link in a flow network
• Finding the n Most Vital Links in Flow Networks
• Finding the most vital arcs in a network
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Most vital links and nodes in weighted networks
• Multi-Terminal Network Flows
• Removing Arcs from a Network
• The k most vital arcs in the shortest path problem

Cited in

(26)

• Minimum cost edge blocker clique problem
• scientific article; zbMATH DE number 3918119 (Why is no real title available?)
• 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
• The quickest root-leaf interdiction problem on tree networks
• Exact algorithms for the minimum cost vertex blocker clique problem
• Connectivity interdiction
• Recoverable robust spanning tree problem under interval uncertainty representations
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Matching interdiction
• The complexity of blocking all solutions
• Optimal cost augmentation and interdiction problem for the minimum spanning tree
• Maximum Capacity Path Interdiction Problem with Fixed Costs
• Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
• A survey on mixed-integer programming techniques in bilevel optimization
• Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization
• Efficient determination of the k most vital edges for the minimum spanning tree problem
• 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
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Approximation algorithms for solving the k-Chinese postman problem under interdiction budget constraints
• Parametric matroid interdiction
• 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)