The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm

DOI10.1002/net.10105zbMath1069.68114OpenAlexW2167459401MaRDI QIDQ4458720

Martine Labbé, Gilbert Laporte, Corinne Feremans

Publication date: 15 March 2004

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10105

zbMATH Keywords

branch-and-cut algorithmnetwork designtelecommunicationstabu search heuristicpolyhedral analysisgeneralized minimum spanning tree

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

A two-level metaheuristic for the all colors shortest path problem, Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems, Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem, A two-level solution approach for solving the generalized minimum spanning tree problem, An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search, Continuous approximation formulas for location problems, A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem, A tabu search heuristic for the generalized minimum spanning tree problem, Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem, The prize-collecting generalized minimum spanning tree problem, The generalized minimum branch vertices problem: properties and polyhedral analysis, The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances, Generalized network design polyhedra

Uses Software

• TSPLIB
• ABACUS

Cites Work

• Unnamed Item
• On the spanning tree polyhedron
• Class Steiner trees and VLSI-design
• Generalized spanning trees
• The class Steiner minimal tree problem: A lower bound and test problem generation
• A note on the generalized Steiner tree polytope
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• A new approach to the maximum-flow problem
• TSPLIB—A Traveling Salesman Problem Library
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• On the generalized minimum spanning tree problem
• The symmetric generalized traveling salesman polytope
• On the facial structure of set packing polyhedra
• Matroids and the greedy algorithm
• On generalized minimum spanning trees