The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances

DOI10.1016/j.ejor.2019.05.017zbMath1431.90166MaRDI QIDQ2286911

Petrică C. Pop

Publication date: 23 January 2020

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2019.05.017

zbMATH Keywords

survey; combinatorial optimization; generalized minimum spanning tree problem

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

Unnamed Item, An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search, Research trends in combinatorial optimization, The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm, Vertex covering with capacitated trees, Partial inverse min-max spanning tree problem, Minimum color spanning circle of imprecise points

Cites Work

• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem
• Distributed data possession checking for securing multiple replicas in geographically-dispersed clouds
• Generalized network design problems. Modeling and optimization.
• A theorem on flows in networks
• Upper and lower bounding strategies for the generalized minimum spanning tree problem
• The geometric generalized minimum spanning tree problem with grid clustering
• 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
• Stochastic spanning tree problem
• Expressing combinatorial optimization problems by linear programs
• Class Steiner trees and VLSI-design
• Solving group Steiner problems as Steiner problems.
• Generalized spanning trees
• Generalized Steiner problems and other variants
• The bi-objective insular traveling salesman problem with maritime and ground transportation costs
• A multigraph formulation for the generalized minimum spanning tree problem
• A two-level solution approach for solving the generalized minimum spanning tree problem
• Large multiple neighborhood search for the clustered vehicle-routing problem
• Generalized network design problems.
• The origins of minimal spanning tree algorithms -- Borůvka and Jarník
• An efficient transformation of the generalized vehicle routing problem
• On the complexity of the selective graph coloring problem in some special classes of graphs
• The prize-collecting generalized minimum spanning tree problem
• On the prize-collecting generalized minimum spanning tree problem
• Iterated local search for the quadratic assignment problem
• A path relinking approach with ejection chains for the generalized assignment problem
• A new relaxation method for the generalized minimum spanning tree problem
• On some applications of the selective graph coloring problem
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• Heuristic Search for the Generalized Minimum Spanning Tree Problem
• The probabilistic minimum spanning tree problem
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• Ant-Tree: an ant colony optimization approach to the generalized minimum spanning tree problem
• The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
• Stochastic maximum weight forest problem
• Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm
• On the generalized minimum spanning tree problem
• The symmetric generalized traveling salesman polytope
• On generalized minimum spanning trees
• Globally and locally minimal weight spanning tree networks