The Steiner tree problem in Kalmanson matrices and in circulant matrices

Authors
Klinz, B Woeginger, GJ
Citation
B. Klinz et Gj. Woeginger, The Steiner tree problem in Kalmanson matrices and in circulant matrices, J COMB OPTI, 3(1), 1999, pp. 51-58
Citations number
11
Categorie Soggetti
Mathematics,"Engineering Mathematics
Journal title
JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN journal
13826905 → ACNP
Volume
3
Issue
1
Year of publication
1999
Pages
51 - 58
Database
ISI
SICI code
1382-6905(199907)3:1<51:TSTPIK>2.0.ZU;2-4
Abstract
We investigate the computational complexity of two special cases of the Ste iner tree problem where the distance matrix is a Kalmanson matrix or a circ ulant matrix, respectively. For Kalmanson matrices we develop an efficient polynomial time algorithm that is based on dynamic programming. For circula nt matrices we give an NP-hardness proof and thus establish computational i ntractability.