The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm

DOI10.1016/j.cor.2010.01.004zbMath1188.90268OpenAlexW1967987311MaRDI QIDQ976040

Abraham P. Punnen, Temel Öncan

Publication date: 11 June 2010

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2010.01.004

zbMATH Keywords

Lagrangian relaxationlocal searchquadratic minimum spanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (16)

MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem ⋮ Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints ⋮ Lower bounds and exact algorithms for the quadratic minimum spanning tree problem ⋮ Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation ⋮ The quadratic minimum spanning tree problem and its variations ⋮ Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem ⋮ Solving the quadratic minimum spanning tree problem ⋮ Combinatorial optimization with one quadratic term: spanning trees and forests ⋮ The minimum spanning tree problem with conflict constraints and its variations ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ Complete description for the spanning tree problem with one linearised quadratic term ⋮ The quadratic shortest path problem: complexity, approximability, and solution methods ⋮ Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ Concentration inequalities for nonlinear matroid intersection ⋮ Unnamed Item

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Fuzzy quadratic minimum spanning tree problem
• On the quadratic assignment problem
• Linear multiplicative programming
• QAPLIB - a quadratic assignment problem library
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• On linear multiplicative programming.
• The Quadratic Assignment Problem
• An Exact Algorithm for the Quadratic Assignment Problem on a Tree
• Tabu Thresholding: Improved Search by Nonmonotonic Trajectories
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• Variable neighborhood search: Principles and applications

This page was built for publication: The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm