Efficient algorithms for finding the k most vital edges for the minimum spanning tree problem

DOI10.1007/978-3-642-22616-8_11zbMATH Open1342.05178OpenAlexW1833577439MaRDI QIDQ5199145FDOQ5199145

Authors: Sonia Toubaline, Daniel Vanderpooten, Cristina Bazgan 

Publication date: 12 August 2011

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22616-8_11

Recommendations

• Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
• scientific article; zbMATH DE number 1444314
• Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\)
• Finding the k most vital edges in the minimum spanning tree problem
• Finding the \(k\) most vital edges with respect to minimum spanning tree

zbMATH Keywords

minimum spanning treeexact algorithmsmixed integer programmost vital edges

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Mixed integer programming (90C11) Enumeration in graph theory (05C30)

Cited In (6)

• Parallel algorithms for finding the most vital edge with respect to minimum spanning tree
• Critical edges/nodes for the minimum spanning tree problem: complexity and approximation
• The most vital edges in the minimum spanning tree problem
• Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem
• A faster computation of the most vital edge of a shortest path
• Finding the most vital edge with respect to minimum spanning tree in weighted graphs

This page was built for publication: Efficient algorithms for finding the \(k\) most vital edges for the minimum spanning tree problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5199145)