Combinatorial optimization with one quadratic term: spanning trees and forests

DOI10.1016/j.dam.2014.05.031zbMath1303.90086OpenAlexW2069579948MaRDI QIDQ406320

Laura Klein, Christoph Buchheim

Publication date: 8 September 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.05.031

zbMATH Keywords

binary quadratic programmingquadratic spanning tree polytope

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items (14)

On the path avoiding forbidden pairs polytope ⋮ Matroid optimisation problems with nested non-linear monomials in the objective function ⋮ Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation ⋮ The quadratic minimum spanning tree problem and its variations ⋮ Combinatorial optimization with one quadratic term: spanning trees and forests ⋮ A characterization of linearizable instances of the quadratic minimum spanning tree problem ⋮ COMPUTATIONAL METHODS FOR LOGISTICS PROBLEMS RELATED TO OPTIMAL TREES ⋮ Complete description for the spanning tree problem with one linearised quadratic term ⋮ An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations ⋮ A class of valid inequalities for multilinear 0-1 optimization problems ⋮ 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 ⋮ Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs ⋮ Multilinear sets with two monomials and cardinality constraints

Uses Software

• SCIL

Cites Work

• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Solving the quadratic minimum spanning tree problem
• Combinatorial optimization with one quadratic term: spanning trees and forests
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• The complexity of a minimum reload cost diameter problem
• Geometric algorithms and combinatorial optimization.
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• The cut polytope and the Boolean quadric polytope
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complete description for the spanning tree problem with one linearised quadratic term
• Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
• On Minimum Changeover Cost Arborescences
• L’algebre de Boole et ses applications en recherche operationnelle
• On The Boolean Quadric Forest Polytope

This page was built for publication: Combinatorial optimization with one quadratic term: spanning trees and forests