The Steiner tree problem in Kalmanson matrices and in circulant matrices

DOI10.1023/A:1009881510868MaRDI QIDQ1304385zbMATH OpenFDO

Authors Bettina Klinz, Gerhard J. Woeginger

Publication date 22 September 1999

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/A:1009881510868

zbMATH Keywords

circulant matrixcomputational complexitydynamic programmingKalmanson matrixpolynomial time algorithmSteiner tree

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• The computational complexity of Steiner tree problems in graded matrices
• The Steiner tree problem
• k-Steiner-minimal-trees in metric spaces

Cited in

(8)

• The computational complexity of Steiner tree problems in graded matrices
• The multi-stripe travelling salesman problem
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• Four-point conditions for the TSP: the complete complexity classification
• The three-dimensional matching problem in kalmanson matrices
• The structure of circular decomposable metrics
• Balancing profits and costs on trees
• A new tractable case of the QAP with a Robinson matrix

This page was built for publication: The Steiner tree problem in Kalmanson matrices and in circulant matrices

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