The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices

We investigate the computational complexity of two special cases of the Steiner tree problem where the distance matrix is a Kalmanson matrix or a circulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circulant matrices we give an -hardness proof and thus establish computational intractability.