The quadratic minimum spanning tree problem and its variations

DOI10.1016/j.disopt.2017.09.003zbMath1506.90256arXiv1603.04451OpenAlexW2962903022MaRDI QIDQ1662110

Ante Ćustić, Abraham P. Punnen, Ruonan Zhang

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

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

zbMATH Keywords

complexitymatroidssparse graphstree enumerationquadratic spanning treerow graded matrix

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (5)

Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem ⋮ A Lagrangian approach for the minimum spanning tree problem with conflicting edge pairs ⋮ An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Solving the quadratic minimum spanning tree problem
• Combinatorial optimization with one quadratic term: spanning trees and forests
• The minimum spanning tree problem with conflict constraints and its variations
• Fuzzy quadratic minimum spanning tree problem
• Paths, trees and matchings under disjunctive constraints
• A survey of very large-scale neighborhood search techniques
• k-sum optimization problems
• The quadratic minimum spanning tree problem: a lower bounding procedure and an efficient search algorithm
• Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem
• Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem
• K-center and K-median problems in graded distances
• The computational complexity of Steiner tree problems in graded matrices
• The quadratic assignment problem. Theory and algorithms
• An effective genetic algorithm approach to the quadratic minimum spanning tree problem
• The doubly graded matrix cone and Ferrers matrices
• The computational complexity of the \(k\)-minimum spanning tree problem in graded matrices
• Quadratic bottleneck knapsack problems
• Complete description for the spanning tree problem with one linearised quadratic term
• Determining a Minimum Spanning Tree with Disjunctive Constraints
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• On the number of spanning trees of finite graphs

This page was built for publication: The quadratic minimum spanning tree problem and its variations