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)

Full work available at URL https://doi.org/10.1016/S0893-9659(97)00056-6

zbMATH Keywords

computational complexitySteiner tree problem

Mathematics Subject Classification ID

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

Review text

The paper considers the computational complexity of the Steiner tree problem in complete graphs, i.e. for a given set \(N\) of vertices in a complete graph \(G=(V,E)\) with a given distance matrix \(D\) it is searched a tree in \(G\) which spans \(N\) with minimal length. In general this problem is NP-hard. Dependent on the gradedness properties of the matrix \(D\), the Steiner tree problem becomes easier. The paper gives polynomial time results for several kinds of such matrices and discusses the sharpeness.

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

(5)

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

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)