The computational complexity of Steiner tree problems in graded matrices

DOI10.1016/S0893-9659(97)00056-6MaRDI QIDQ1372300zbMATH OpenFDO

Authors Tibor Dudás, Bettina Klinz, Gerhard J. Woeginger

Publication date 9 December 1997

Published in Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

computational complexitySteiner tree problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The computational complexity of the k-minimum spanning tree problem in graded matrices
• The Steiner tree problem in Kalmanson matrices and in circulant matrices
• scientific article; zbMATH DE number 970831
• scientific article; zbMATH DE number 1532673

Cites work

• scientific article; zbMATH DE number 4027206 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• The Complexity of Computing Steiner Minimal Trees
• The Steiner tree problem

Cited in

(4)

• K-center and K-median problems in graded distances
• Classes of directed graded graphs with polynomially solvable cardinality Steiner problem
• The computational complexity of the k-minimum spanning tree problem in graded matrices
• The quadratic minimum spanning tree problem and its variations

This page was built for publication: The computational complexity of Steiner tree problems in graded matrices

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