A characterization of linearizable instances of the quadratic minimum spanning tree problem

DOI10.1007/S10878-017-0184-3MaRDI QIDQ1702825zbMATH OpenOpenAlexFDO

Authors Ante Ćustić, Abraham P. Punnen

Publication date 1 March 2018

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.02197

zbMATH Keywords

linearizationminimum spanning treepolynomially solvable casesquadratic \(0-1\) problemsquadratic minimum spanning tree

Mathematics Subject Classification ID

Boolean programming (90C09) Quadratic programming (90C20) Programming involving graphs or networks (90C35)

Abstract: We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph $G=(V,E)$ that can be solved as a linear minimum spanning tree problem. Characterization of such problems on graphs with special properties are given. This include complete graphs, complete bipartite graphs, cactuses among others. Our characterization can be verified in $O(|E{|}^2)$ time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in $O(|E|)$ time. Related open problems are also indicated.

Recommendations

• Complete description for the spanning tree problem with one linearised quadratic term
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• scientific article; zbMATH DE number 35513
• The quadratic minimum spanning tree problem and its variations

Cites work

• A contribution to quadratic assignment problems
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• An FPTAS for minimizing the product of two non-negative linear cost functions
• An FPTAS for optimizing a class of low-rank functions over a polytope
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Complete description for the spanning tree problem with one linearised quadratic term
• Fuzzy quadratic minimum spanning tree problem
• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• Linear programming insights into solvable cases of the quadratic assignment problem
• Linearizable special cases of the QAP
• 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
• Paths, trees and matchings under disjunctive constraints
• Quadratic programming and combinatorial minimum weight product problems
• Solving the quadratic minimum spanning tree problem
• The bilinear assignment problem: complexity and polynomially solvable special cases
• The minimum spanning tree problem with conflict constraints and its variations
• The quadratic minimum spanning tree problem and its variations
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm

Cited in

(21)

• The quadratic minimum spanning tree problem and its variations
• On a linearization technique for solving the quadratic set covering problem and variations
• The bilinear assignment problem: complexity and polynomially solvable special cases
• Special cases of the quadratic shortest path problem
• Combinatorial optimization with interaction costs: complexity and solvable cases
• The linearization problem of a binary quadratic problem and its applications
• The quadratic cycle cover problem: special cases and efficient bounds
• Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem
• Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• Complete description for the spanning tree problem with one linearised quadratic term
• Linearizable special cases of the quadratic shortest path problem
• Solving the quadratic minimum spanning tree problem
• On Linear Recognition of Tree-Width at Most Four
• Polyhedral results, branch‐and‐cut and Lagrangian relaxation algorithms for the adjacent only quadratic minimum spanning tree problem
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint
• A polyhedral characterization of linearizable quadratic combinatorial optimization problems
• The quadratic minimum spanning tree problem: lower bounds via extended formulations
• The independent quadratic assignment problem: complexity and polynomially solvable special cases
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems

This page was built for publication: A characterization of linearizable instances of 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 Q1702825)