The Steiner tree problem in Kalmanson matrices and in circulant matrices

B. Klinz, G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    6 Citations (Scopus)

    Abstract

    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 NP -hardness proof and thus establish computational intractability.
    Original languageEnglish
    Pages (from-to)51-58
    Number of pages8
    JournalJournal of Combinatorial Optimization
    Volume3
    Issue number1
    DOIs
    Publication statusPublished - 1999

    Fingerprint Dive into the research topics of 'The Steiner tree problem in Kalmanson matrices and in circulant matrices'. Together they form a unique fingerprint.

  • Cite this