Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

DOI10.1016/j.cor.2015.04.020zbMath1349.90823OpenAlexW321511787MaRDI QIDQ342052

Michel Gendreau, Alexandre Salles da Cunha, Dilson Lucas Pereira

Publication date: 17 November 2016

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

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

zbMATH Keywords

Lagrangian relaxationquadratic 0-1 programmingspanning trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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, A characterization of linearizable instances of the quadratic minimum spanning tree problem, 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Solving the quadratic minimum spanning tree problem
• Non delayed relax-and-cut algorithms
• The quadratic knapsack problem -- a survey
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A parallel depth first search branch and bound algorithm for the quadratic assignment problem
• Constrained weighted matchings and edge coverings in graphs
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• Branching rules revisited
• Constrained 0-1 quadratic programming: basic approaches and extensions
• The Quadratic Assignment Problem
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Validation of subgradient optimization
• Maximum matching and a polyhedron with 0,1-vertices
• Matroids and the greedy algorithm
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• On The Boolean Quadric Forest Polytope