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

DOI10.1016/J.COR.2010.01.004MaRDI QIDQ976040zbMATH OpenOpenAlexFDO

Authors Temel Öncan, Abraham P. Punnen

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

local searchLagrangian relaxationquadratic minimum spanning tree problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• scientific article; zbMATH DE number 35513
• Solving the quadratic minimum spanning tree problem
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem

Cites work

• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• scientific article; zbMATH DE number 795222 (Why is no real title available?)
• An Exact Algorithm for the Quadratic Assignment Problem on a Tree
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• Fuzzy quadratic minimum spanning tree problem
• Linear multiplicative programming
• On linear multiplicative programming.
• On the quadratic assignment problem
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• QAPLIB - a quadratic assignment problem library
• Tabu Thresholding: Improved Search by Nonmonotonic Trajectories
• The quadratic assignment problem
• Variable neighborhood search: Principles and applications

Cited in

(21)

• The quadratic shortest path problem: complexity, approximability, and solution methods
• Dynamic Programming Driven Memetic Search for the Steiner Tree Problem with Revenues, Budget, and Hop Constraints
• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• Concentration inequalities for nonlinear matroid intersection
• Quadratic bottleneck problems
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
• MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem
• Matroid optimization problems with monotone monomials in the objective
• Spanning and splitting: integer semidefinite programming for the quadratic minimum spanning tree problem
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Combinatorial optimization with one quadratic term: spanning trees and forests
• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• Solving the quadratic minimum spanning tree problem
• Complete description for the spanning tree problem with one linearised quadratic term
• Concentration inequalities for nonlinear matroid intersection
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem
• The minimum spanning tree problem with conflict constraints and its variations
• The quadratic minimum spanning tree problem: lower bounds via extended formulations
• The quadratic minimum spanning tree problem and its variations

Describes a project that uses

Uses Software

• QAPLIB

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976040)