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

minimum spanning treelinearizationquadratic minimum spanning treepolynomially solvable casesquadratic \(0-1\) problems

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• A contribution to quadratic assignment problems
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• 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
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• 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
• 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

(17)

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