On a quadratic programming problem involving distances in trees

DOI10.1007/S10479-014-1743-YMaRDI QIDQ338937zbMATH OpenOpenAlexFDO

Authors S. K. Neogy, R. B. Bapat

Publication date 7 November 2016

Published in Annals of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10479-014-1743-y

zbMATH Keywords

treedistance matrixquadratic programming problempolynomial timefinite metric spaceLemke's algorithmsymmetric bimatrix game

Mathematics Subject Classification ID

Quadratic programming (90C20) Trees (05C05) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 35513
• Dynamic programming for the quadratic assignment problem on trees
• The quadratic minimum spanning tree problem and its variations
• An Exact Algorithm for the Quadratic Assignment Problem on a Tree
• Solving the quadratic minimum spanning tree problem
• Improved methods for computing distances between unordered trees using integer programming
• Distance Approximating Trees: Complexity and Algorithms
• Distance approximating trees in graphs
• On distances in vertex-weighted trees
• A linear time algorithm for the \(p\)-maxian problem on trees with distance constraint

Cites work

• scientific article; zbMATH DE number 53115 (Why is no real title available?)
• scientific article; zbMATH DE number 1033392 (Why is no real title available?)
• scientific article; zbMATH DE number 3432469 (Why is no real title available?)
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A polynomial-time algorithm for a class of linear complementarity problems
• Average distance in weighted graphs
• Bimatrix Equilibrium Points and Mathematical Programming
• Finite metric spaces of strictly negative type
• Identities for minors of the Laplacian, resistance and distance matrices
• On a conjecture concerning spanning tree invariants and loop systems
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• Some NP-complete problems in quadratic and nonlinear programming
• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm

Cited in

(5)

• Solving the quadratic minimum spanning tree problem
• Variance and covariance of distributions on graphs
• On solving a non-convex quadratic programming problem involving resistance distances in graphs
• Maximization of quadratic forms expressed by distance matrices
• Optimizing quadratic forms of adjacency matrices of trees and related eigenvalue problems

This page was built for publication: On a quadratic programming problem involving distances in trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q338937)