The tree-star problem: a formulation and a branch-and-cut algorithm

DOI10.1016/J.ENDM.2016.03.038zbMATH Open1351.90051OpenAlexW2408068853MaRDI QIDQ325465FDOQ325465

Authors: Abilio Lucena, L. Simonetti, Alexandre Salles da Cunha 

Publication date: 18 October 2016

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

Recommendations

• A branch and cut method for the degree-constrained minimum spanning tree problem
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
• Branch-and-cut-and-price algorithms for the degree constrained minimum spanning tree problem
• Mixed-integer programming approaches for the tree \(t^*\)-spanner problem

zbMATH Keywords

formulationbranch-and-cut algorithmtree-star problem

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Strong lower bounds for the prize collecting Steiner problem in graphs
• The Ring Star Problem: Polyhedral analysis and exact algorithm
• The minimum connected dominating set problem: formulation, valid inequalities and a branch-and-cut algorithm
• The ring-star problem: a new integer programming formulation and a branch-and-cut algorithm
• Reformulations and solution algorithms for the maximum leaf spanning tree problem

Cited In (7)

• Branch‐and‐cut algorithms for the ‐arborescence star problem
• A new formulation for spanning trees
• Mixed-integer programming approaches for the tree \(t^*\)-spanner problem
• The complete optimal stars-clustering-tree problem
• On the Optimal Stars Clustering Tree Problem
• The solutions of two star-height problems for regular trees
• An algorithmic framework for the exact solution of tree-star problems

Uses Software

• TSPLIB

This page was built for publication: The tree-star problem: a formulation and a branch-and-cut algorithm

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