| Autor: |
Çela, E., Schmuck, N.S., Wimer, S., Woeginger, G.J. |
| Přispěvatelé: |
Combinatorial Optimization 1, Discrete Mathematics |
| Jazyk: |
angličtina |
| Rok vydání: |
2011 |
| Popis: |
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. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
