A comparative analysis of several formulations for the generalized minimum spanning tree problem

DOI10.1002/NET.10009zbMath1001.90066OpenAlexW2110105948MaRDI QIDQ2782729

Gilbert Laporte, Martine Labbé, Corinne Feremans

Publication date: 8 April 2002

Published in: Networks (Search for Journal in Brave)

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

zbMATH Keywords

polytopesspanning treesinteger linear pogramming

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (21)

A two-level metaheuristic for the all colors shortest path problem ⋮ Generalized minimum spanning tree games ⋮ An automated network generation procedure for routing of unmanned aerial vehicles (UAVs) in a GIS environment ⋮ A two-level solution approach for solving the generalized minimum spanning tree problem ⋮ Continuous approximation formulas for location problems ⋮ A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem ⋮ The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches ⋮ Solving group Steiner problems as Steiner problems. ⋮ A tabu search heuristic for the generalized minimum spanning tree problem ⋮ Preprocessing for a map sectorization problem by means of mathematical programming ⋮ Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem ⋮ The prize-collecting generalized minimum spanning tree problem ⋮ On the prize-collecting generalized minimum spanning tree problem ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ 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 ⋮ Approximation algorithms for group prize-collecting and location-routing problems ⋮ Generalized network design problems. ⋮ The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm ⋮ A new relaxation method for the generalized minimum spanning tree problem ⋮ Upper and lower bounding strategies for the generalized minimum spanning tree problem

Cites Work

• A theorem on flows in networks
• On the generalized minimum spanning tree problem
• A catalog of steiner tree formulations

This page was built for publication: A comparative analysis of several formulations for the generalized minimum spanning tree problem