Premium
The quadratic minimum spanning tree problem
Author(s) -
Assad Arjang,
Xu Weixuan
Publication year - 1992
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199204)39:3<399::aid-nav3220390309>3.0.co;2-0
Subject(s) - minimum spanning tree , spanning tree , heuristic , mathematical optimization , quadratic equation , mathematics , distributed minimum spanning tree , branch and bound , tree (set theory) , k minimum spanning tree , kruskal's algorithm , steiner tree problem , computer science , combinatorics , tree structure , k ary tree , binary tree , geometry
This article introduces a new optimization problem that involves searching for the spanning tree of minimum cost under a quadratic cost structure. This quadratic minimum spanning tree problem is proven to be NP‐hard. A technique for generating lower bounds for this problem is discussed and incorporated into branch‐and‐bound schemes for obtaining exact solutions. Two heuristic algorithms are also developed. Computational experience with both exact and heuristic algorithms is reported.