The Wiener maximum quadratic assignment problem

Details The Wiener maximum quadratic assignment problem The Wiener maximum quadratic assignment problem

2011-02-15

arxiv.org/abs/1102.3030v3

Mathematics

Optimization and Control

11 pages, no figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Wiener maximum quadratic assignment problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Wiener maximum quadratic assignment problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Wiener maximum quadratic assignment problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378249