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

DOI10.1016/J.EJOR.2015.04.011zbMATH Open1346.90789OpenAlexW2041365558MaRDI QIDQ319657FDOQ319657

Authors 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) Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
• An exact and heuristic approach for the \(d\)-minimum branch vertices problem
• An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
• Lower and upper bounds for the spanning tree with minimum branch vertices
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices

Cites Work

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

Cited In (17)

• Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
• The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms
• Approximating spanning trees with few branches
• An exact and heuristic approach for the \(d\)-minimum branch vertices problem
• The generalized minimum branch vertices problem: properties and polyhedral analysis
• A genetic approach for the 2‐edge‐connected minimum branch vertices problem
• Title not available (Why is no real title available?)
• Spanning Trees with Few Branch Vertices
• Lower and upper bounds for the spanning tree with minimum branch vertices
• The tree-star problem: a formulation and a branch-and-cut algorithm
• 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
• Upper and lower bounding procedures for the minimum caterpillar spanning problem
• Decomposition methods based on articulation vertices for degree-dependent spanning tree problems
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
• Approximating spanning trees with few branches
• Cutting-plane-based algorithms for two branch vertices related spanning tree problems

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

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