Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)

DOI10.1016/S0166-218X(01)00189-5zbMath0991.68057OpenAlexW2045966094MaRDI QIDQ5951977

Weifa Liang

Publication date: 8 January 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00189-5

zbMATH Keywords

combinatorial algorithmsminimum spanning trees

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items

\(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs ⋮ Critical edges/nodes for the minimum spanning tree problem: complexity and approximation ⋮ A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths ⋮ Parametric matroid interdiction ⋮ Critical edges for the assignment problem: complexity and exact resolution ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under Hamming distance ⋮ Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem ⋮ Maximum shortest path interdiction problem by upgrading edges on trees under weighted \(l_1\) norm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Finding the k most vital edges in the minimum spanning tree problem
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• Efficient algorithms for finding the most vital edge of a minimum spanning tree
• Finding the \(k\) most vital edges with respect to minimum spanning tree
• Optimal parallel verification of minimum spanning trees in logarithmic time
• Efficient parallel algorithms for some graph problems
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• A randomized linear-time algorithm to find minimum spanning trees
• A simple parallel tree contraction algorithm