Upper and lower bounding strategies for the generalized minimum spanning tree problem

DOI10.1016/j.ejor.2004.07.072zbMath1090.90163OpenAlexW2023571729MaRDI QIDQ817552

Mohamed Haouari, Jouhaina Siala Chaouachi

Publication date: 16 March 2006

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

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

zbMATH Keywords

Lagrangian relaxationgenetic algorithmSteiner treegeneralized minimum spanning treerandomized greedy heuristic

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A two-level solution approach for solving the generalized minimum spanning tree problem, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, A tabu search heuristic for the generalized minimum spanning tree problem, A rapid learning automata-based approach for generalized minimum spanning tree problem, The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The full Steiner tree problem
• The Steiner tree problem
• Class Steiner trees and VLSI-design
• Solving group Steiner problems as Steiner problems.
• Generalized spanning trees
• Guided local search and its application to the traveling salesman problem
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• A dual ascent approach for steiner tree problems on a directed graph
• An SST-based algorithm for the steiner problem in graphs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Feature Article—Genetic Algorithms for the Operations Researcher
• Ant-Tree: an ant colony optimization approach to the generalized minimum spanning tree problem
• A probabilistic greedy search algorithm for combinatorial optimisation with application to the set covering problem
• On the History of the Minimum Spanning Tree Problem
• On the generalized minimum spanning tree problem
• A catalog of steiner tree formulations
• On generalized minimum spanning trees
• Globally and locally minimal weight spanning tree networks