Finding the k most vital edges in the minimum spanning tree problem

DOI10.1016/S0167-8191(97)00098-7MaRDI QIDQ1127438zbMATH OpenOpenAlexFDO

Authors W. Liang, Xiaojun Shen

Publication date 13 August 1998

Published in Parallel Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0167-8191(97)00098-7

zbMATH Keywords

combinatorial algorithmsminimum spanning treesmost vital edgesNC algorithmsnetwork optimization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• scientific article; zbMATH DE number 1444314
• Finding the k most vital edges with respect to minimum spanning tree
• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree

Cited in

(15)

• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• Blocking unions of arborescences
• Efficient determination of the k most vital edges for the minimum spanning tree problem
• Finding the k most vital edges with respect to minimum spanning tree
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree^∗
• scientific article; zbMATH DE number 1796972 (Why is no real title available?)
• scientific article; zbMATH DE number 1444314 (Why is no real title available?)
• Integer Programming Formulations for Minimum Spanning Tree Interdiction
• Efficient algorithms for finding the k most vital edges for the minimum spanning tree problem
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• Parametric matroid interdiction
• NC algorithms for the Single Most Vital Edge problem with respect to shortest paths
• Optimal cost augmentation and interdiction problem for the minimum spanning tree
• The parametric matroid -interdiction problem

This page was built for publication: Finding the k 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 Q1127438)