The Wiener maximum quadratic assignment problem
From MaRDI portal
Abstract: 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 5627542 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 508964 (Why is no real title available?)
- A solvable case of the quadratic assignment problem
- Assignment Problems
- Assignment Problems and the Location of Economic Activities
- Corrigendum: The extremal values of the Wiener index of a tree with given degree sequence
- Distance in graphs
- The extremal values of the Wiener index of a tree with given degree sequence
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- The quadratic assignment problem. Theory and algorithms
- Wiener index of trees: Theory and applications
- Wiener index versus maximum degree in trees
Cited in
(29)- On distances in vertex-weighted trees
- Steiner Wiener index of block graphs
- Maximum external Wiener index of graphs
- Sum of weighted distances in trees
- Maximizing Wiener index for trees with given vertex weight and degree sequences
- On the maximal Wiener index and related questions
- Some extremal ratios of the distance and subtree problems in binary trees
- Eccentricity sums in trees
- New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
- Wiener index in graphs with given minimum degree and maximum degree
- Linear programming insights into solvable cases of the quadratic assignment problem
- The minimal number of subtrees of a tree
- The minimal number of subtrees with a given degree sequence
- A new tractable case of the QAP with a Robinson matrix
- A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
- Another well-solvable case of the QAP: maximizing the job completion time variance
- Complexity and polynomially solvable special cases of QUBO
- The distances between internal vertices and leaves of a tree
- Well-solvable cases of the QAP with block-structured matrices
- Proof of a conjecture on the Wiener index of Eulerian graphs
- Steiner Wiener index and line graphs of trees
- On Wiener index and average eccentricity of graphs of girth at least 6 and \((C_4, C_5)\)-free graphs
- A new algorithm for solving a special matching problem with a general form value function under constraints
- On the distance spectral radius of trees with given degree sequence
- Split sizes and extremal tree shapes
- Extreme Wiener indices of trees with given number of vertices of maximum degree
- Graph similarity and approximate isomorphism
- Special cases of the quadratic shortest path problem
- Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
This page was built for publication: The Wiener maximum quadratic assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q665991)
