The Wiener maximum quadratic assignment problem

DOI10.1016/j.disopt.2011.02.002zbMath1233.90282arXiv1102.3030MaRDI QIDQ665991

Shmuel Wimer, Nina S. Schmuck, Eranda Çela, Gerhard J. Woeginger

Publication date: 7 March 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1102.3030

zbMATH Keywords

computational complexity; combinatorial optimization; graph theory; Wiener index; degree sequence

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C27: Combinatorial optimization

90B80: Discrete location and assignment

Related Items

Unnamed Item, Steiner Wiener index of block graphs, Wiener index in graphs with given minimum degree and maximum degree, Complexity and Polynomially Solvable Special Cases of QUBO, Graph Similarity and Approximate Isomorphism, A New Tractable Case of the QAP with a Robinson Matrix, Eccentricity sums in trees, On the maximal Wiener index and related questions, The minimal number of subtrees of a tree, The minimal number of subtrees with a given degree sequence, Split sizes and extremal tree shapes, The distances between internal vertices and leaves of a tree, A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems, Sum of weighted distances in trees, Maximum external Wiener index of graphs, Maximizing Wiener index for trees with given vertex weight and degree sequences, Special cases of the quadratic shortest path problem, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, Another well-solvable case of the QAP: maximizing the job completion time variance, Proof of a conjecture on the Wiener index of Eulerian graphs, Extreme Wiener indices of trees with given number of vertices of maximum degree, Some extremal ratios of the distance and subtree problems in binary trees, 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, On distances in vertex-weighted trees, Linear programming insights into solvable cases of the quadratic assignment problem, Well-solvable cases of the QAP with block-structured matrices, On Wiener index and average eccentricity of graphs of girth at least 6 and \((C_4, C_5)\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The extremal values of the Wiener index of a tree with given degree sequence
• Corrigendum: The extremal values of the Wiener index of a tree with given degree sequence
• 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
• Assignment Problems
• Distance in graphs
• Wiener index of trees: Theory and applications