An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices

DOI10.1007/s10589-016-9850-0zbMath1357.90123arXiv1509.06562OpenAlexW2240396129MaRDI QIDQ2374371

Sebastián Urrutia, Phillippe Samer, Rafael A. Melo

Publication date: 15 December 2016

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.06562

zbMATH Keywords

heuristicscombinatorial optimizationbranch and cutspanning treegraph decompositionminimum branch vertices

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (6)

A branch-and-cut algorithm for the minimum branch vertices spanning tree problem ⋮ Maximum weighted induced forests and trees: new formulations and a computational comparative review ⋮ Decomposition methods based on articulation vertices for degree-dependent spanning tree problems ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ An exact and heuristic approach for the \(d\)-minimum branch vertices problem ⋮ Spanning Trees with Few Branch Vertices

Cites Work

• 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
• Spanning trees with a bounded number of branch vertices in a claw-free graph
• Spanning spiders and light-splitting switches
• Relations, models and a memetic approach for three degree-dependent spanning tree problems
• Cutting-plane-based algorithms for two branch vertices related spanning tree problems
• An edge-swap heuristic for generating spanning trees with minimum number of branch vertices
• Approximating Spanning Trees with Few Branches
• A graph coloring algorithm for large scheduling problems

This page was built for publication: An effective decomposition approach and heuristics to generate spanning trees with a small number of branch vertices