Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem

DOI10.1016/J.EJOR.2015.04.011zbMath1346.90789OpenAlexW2041365558MaRDI QIDQ319657

Alfredo Marín

Publication date: 6 October 2016

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2015.04.011

zbMATH Keywords

integer programmingspanning treebranch vertices

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (7)

An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices ⋮ A branch-and-cut algorithm for the minimum branch vertices spanning tree problem ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ A genetic approach for the 2‐edge‐connected minimum branch vertices problem ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ Spanning Trees with Few Branch Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Looking for edge-equitable spanning trees
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Bounded-degree spanning tree problems: models and new algorithms
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• Tight bounds from a path based formulation for the tree of hub location problem
• A simple test on 2-vertex- and 2-edge-connectivity
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• On finding spanning trees with few leaves
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
• Integer Programming Formulation of Traveling Salesman Problems
• On Local Search and Placement of Meters in Networks

This page was built for publication: Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem