The Wiener maximum quadratic assignment problem

E. Çela, N.S. Schmuck, S. Wimer, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

32 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
Pagina's (van-tot)411-416
TijdschriftDiscrete Optimization
Volume8
Nummer van het tijdschrift3
DOI's
StatusGepubliceerd - 2011

Vingerafdruk

Duik in de onderzoeksthema's van 'The Wiener maximum quadratic assignment problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit