The Steiner tree problem in Kalmanson matrices and in circulant matrices
From MaRDI portal
Publication:1304385
DOI10.1023/A:1009881510868zbMath0936.05032MaRDI QIDQ1304385
Bettina Klinz, Gerhard J. Woeginger
Publication date: 22 September 1999
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
computational complexitydynamic programmingpolynomial time algorithmcirculant matrixSteiner treeKalmanson matrix
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorial optimization (90C27) Dynamic programming (90C39) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
The three-dimensional matching problem in kalmanson matrices, Balancing profits and costs on trees, The multi-stripe travelling salesman problem, New special cases of the quadratic assignment problem with diagonally structured coefficient matrices, A New Tractable Case of the QAP with a Robinson Matrix, Four-point conditions for the TSP: the complete complexity classification