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

DOI10.1007/978-3-642-22616-8_11MaRDI QIDQ5199145zbMATH OpenOpenAlexFDO

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

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)

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

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)