A new formulation for spanning trees

DOI10.1016/J.ENDM.2011.05.034MaRDI QIDQ2840708zbMATH OpenOpenAlexFDO

Authors Sebastián Urrutia, Abilio Lucena

Publication date 23 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2011.05.034

zbMATH Keywords

spanning treesinteger programing

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Integer programming (90C10)

Recommendations

• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem
• Solving diameter-constrained minimum spanning tree problems by constraint programming
• Integer programming formulations for minimum spanning forests and connected components in sparse graphs
• The tree-star problem: a formulation and a branch-and-cut algorithm
• A new relaxation method for the generalized minimum spanning tree problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Matroids and the greedy algorithm
• Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs

Cited in

(6)

• Characterizing acyclic graphs by labeling edges
• Constraint Programming for the Diameter Constrained Minimum Spanning Tree Problem
• Integer programming formulations for minimum spanning forests and connected components in sparse graphs
• Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
• scientific article; zbMATH DE number 4173002 (Why is no real title available?)
• Emerging spanning trees in the work of Candilis-Josic-Woods

This page was built for publication: A new formulation for spanning trees

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