The computational complexity of Steiner tree problems in graded matrices (Q1372300)

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.