Integer programming formulations for minimum spanning forests and connected components in sparse graphs

DOI10.1007/978-3-319-12691-3_46MaRDI QIDQ2942437zbMATH OpenOpenAlexFDO

Authors Neng Fan, Mehdi Golari

Publication date 11 September 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-12691-3_46

zbMATH Keywords

minimum spanning treeinteger programmingconnected componentsminimum spanning forestnetwork vulnerability analysis

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10)

Recommendations

• Formulations and branch-and-cut algorithm for the \(K\)-rooted mini-max spanning forest problem
• A new formulation for spanning trees
• scientific article; zbMATH DE number 5621997
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• An efficient mixed integer linear programming model for the minimum spanning tree problem

Cited in

(5)

• A new formulation for spanning trees
• Sparsity of integer formulations for binary programs
• Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles
• Optimal connected subgraphs: Integer programming formulations and polyhedra
• Cost optimized design for the local wind turbine grid of an onshore wind farm

This page was built for publication: Integer programming formulations for minimum spanning forests and connected components in sparse graphs

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