The Wiener maximum quadratic assignment problem
From MaRDI portal
Publication:665991
DOI10.1016/J.DISOPT.2011.02.002zbMATH Open1233.90282arXiv1102.3030OpenAlexW2157904603MaRDI QIDQ665991FDOQ665991
Authors: Eranda Çela, Nina S. Schmuck, Shmuel Wimer, Gerhard J. Woeginger 
Publication date: 7 March 2012
Published in: Discrete Optimization (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1102.3030
Recommendations
Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)
Cites Work
- Assignment Problems
- Title not available (Why is that?)
- A solvable case of the quadratic assignment problem
- 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 versus maximum degree in trees
- Assignment Problems and the Location of Economic Activities
- Wiener index of trees: Theory and applications
- Distance in graphs
- Title not available (Why is that?)
- The extremal values of the Wiener index of a tree with given degree sequence
- Title not available (Why is that?)
- Corrigendum: The extremal values of the Wiener index of a tree with given degree sequence
Cited In (29)
- Steiner Wiener index of block graphs
- On distances in vertex-weighted trees
- 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
- Wiener index in graphs with given minimum degree and maximum degree
- Eccentricity sums in trees
- New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
- Linear programming insights into solvable cases of the quadratic assignment problem
- A new tractable case of the QAP with a Robinson matrix
- The minimal number of subtrees of a tree
- The minimal number of subtrees with a given degree sequence
- A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
- Complexity and polynomially solvable special cases of QUBO
- Another well-solvable case of the QAP: maximizing the job completion time variance
- The distances between internal vertices and leaves of a tree
- Well-solvable cases of the QAP with block-structured matrices
- Steiner Wiener index and line graphs of trees
- Proof of a conjecture on the Wiener index of Eulerian graphs
- 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
- Graph similarity and approximate isomorphism
- Extreme Wiener indices of trees with given number of vertices of maximum degree
- Split sizes and extremal tree shapes
- Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
- Special cases of the quadratic shortest path problem
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)
