The Wiener maximum quadratic assignment problem
The Wiener maximum quadratic assignment problem
复制标题
DOI：
10.1016/j.disopt.2011.02.002
复制
发表时间：
2011-02
期刊：
影响因子：
--
通讯作者：
E. Çela;Nina S. Schmuck;S. Wimer;G. Woeginger
中科院分区：
文献类型：
--
作者：
E. Çela;Nina S. Schmuck;S. Wimer;G. Woeginger
本文研究了最大二次分配问题的一种特殊情况，其中一个矩阵是一维点集的乘积矩阵，另一个矩阵是一维点集的距离矩阵。我们表明，这种特殊的情况下，我们称之为维纳最大二次分配问题，是NP-硬在普通意义下，在伪多项式时间内可解。我们的方法也产生了一个多项式时间的解决方案，从化学图论的以下问题：找到一棵树，最大化的维纳指数在所有的树与规定的程度序列。这解决了文献中的一个公开问题。
We investigate a special case of the maximum quadratic assignment problem where one matrix is a product matrix and the other matrix is the distance matrix of a one-dimensional point set. We show that this special case, which we call the Wiener maximum quadratic assignment problem, is NP-hard in the ordinary sense and solvable in pseudo-polynomial time. Our approach also yields a polynomial time solution for the following problem from chemical graph theory: find a tree that maximizes the Wiener index among all trees with a prescribed degree sequence. This settles an open problem from the literature.