The Wiener maximum quadratic assignment problem

DOI10.1016/j.disopt.2011.02.002zbMath1233.90282arXiv1102.3030OpenAlexW2157904603MaRDI 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 complexitycombinatorial optimizationgraph theoryWiener indexdegree sequence

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items (29)

Wiener index in graphs with given minimum degree and maximum degree ⋮ Eccentricity sums in trees ⋮ Complexity and Polynomially Solvable Special Cases of QUBO ⋮ A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems ⋮ Characterizing linearizable QAPs by the level-1 reformulation-linearization technique ⋮ On Wiener index and average eccentricity of graphs of girth at least 6 and \((C_4, C_5)\)-free graphs ⋮ On the maximal Wiener index and related questions ⋮ Sum of weighted distances in trees ⋮ Maximum external Wiener index of graphs ⋮ The minimal number of subtrees of a tree ⋮ The minimal number of subtrees with a given degree sequence ⋮ Extreme Wiener indices of trees with given number of vertices of maximum degree ⋮ Split sizes and extremal tree shapes ⋮ Graph Similarity and Approximate Isomorphism ⋮ Maximizing Wiener index for trees with given vertex weight and degree sequences ⋮ Special cases of the quadratic shortest path problem ⋮ Unnamed Item ⋮ 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 ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ Some extremal ratios of the distance and subtree problems in binary trees ⋮ Proof of a conjecture on the Wiener index of Eulerian graphs ⋮ A new algorithm for solving a special matching problem with a general form value function under constraints ⋮ Steiner Wiener index of block graphs ⋮ The distances between internal vertices and leaves of a tree ⋮ 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

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

This page was built for publication: The Wiener maximum quadratic assignment problem