The Wiener maximum quadratic assignment problem

被引：33

作者：

Cela, Eranda ^{[1
]}

Schmuck, Nina S. ^{[1
]}

Wimer, Shmuel ^{[2
]}

Woeginger, Gerhard J. ^{[3
]}

机构：

[1] Graz Univ Technol, Inst Optimierung & Diskrete Math, A-8010 Graz, Austria

[2] Bar Ilan Univ, Sch Engn, IL-52900 Ramat Gan, Israel

[3] TU Eindhoven, Dept Math & Comp Sci, NL-5600 MB Eindhoven, Netherlands

来源：

DISCRETE OPTIMIZATION | 2011年 / 8卷 / 03期

关键词：

Combinatorial optimization; Computational complexity; Graph theory; Degree sequence; Wiener index; INDEX; TREES;

D O I：

10.1016/j.disopt.2011.02.002

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：411 / 416

页数：6

共 15 条

[1]

[Anonymous], 1998, The Quadratic Assignment Problem Theory and Algorithm

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[3]

Burkard R., 2009, ASSIGNMENT PROBLEMS

[4] The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases [J].