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

DOI10.1016/J.COR.2015.04.020zbMATH Open1349.90823OpenAlexW321511787MaRDI QIDQ342052FDOQ342052

Authors: Dilson Lucas Pereira, Michel Gendreau, Alexandre Salles da Cunha 

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

Recommendations

• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• scientific article; zbMATH DE number 35513
• Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem

zbMATH Keywords

spanning treesLagrangian relaxationquadratic 0-1 programming

Mathematics Subject Classification ID

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

Cites Work

• The quadratic knapsack problem -- a survey
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Branching rules revisited
• 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
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Matroids and the greedy algorithm
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The quadratic assignment problem
• Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
• Solving the quadratic minimum spanning tree problem
• Title not available (Why is that?)
• A parallel depth first search branch and bound algorithm for the quadratic assignment problem
• Constrained weighted matchings and edge coverings in graphs
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• Constrained 0-1 quadratic programming: basic approaches and extensions
• On The Boolean Quadric Forest Polytope
• Non delayed relax-and-cut algorithms

Cited In (13)

• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• 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
• Matroid optimization problems with monotone monomials in the objective
• Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Title not available (Why is that?)
• Complete description for the spanning tree problem with one linearised quadratic term
• Solving the quadratic minimum spanning tree problem
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem
• The quadratic minimum spanning tree problem and its variations
• Quadratic lower bounds for algebraic branching programs and formulas

This page was built for publication: Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

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