A branch-and-cut algorithm for the minimum branch vertices spanning tree problem

DOI10.1016/j.cor.2016.11.010zbMath1391.90619DBLPjournals/cor/SilvestriLC17OpenAlexW2550142813WikidataQ56524258 ScholiaQ56524258MaRDI QIDQ1652257

Raffaele Cerulli, Selene Silvestri, Gilbert Laporte

Publication date: 11 July 2018

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2016.11.010

zbMATH Keywords

spanning treebranch-and-cutbranch vertices

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (8)

Improved approaches to solve the one-to-one skewgram 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 ⋮ A hybrid steady-state genetic algorithm for the min-degree constrained minimum spanning tree problem ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ The generalized minimum branch vertices problem: properties and polyhedral analysis ⋮ Spanning Trees with Few Branch Vertices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• Lower and upper bounds for the spanning tree with minimum branch vertices
• Bounded-degree spanning tree problems: models and new algorithms
• Reformulations and solution algorithms for the maximum leaf spanning tree problem
• A simple test on 2-vertex- and 2-edge-connectivity
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
• Integer Programming
• Integer Programming Formulation of Traveling Salesman Problems
• Trees and Cuts
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Solution of a Large-Scale Traveling-Salesman Problem

This page was built for publication: A branch-and-cut algorithm for the minimum branch vertices spanning tree problem