Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
From MaRDI portal
Publication:5951977
DOI10.1016/S0166-218X(01)00189-5zbMath0991.68057OpenAlexW2045966094MaRDI QIDQ5951977
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
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
