The Steiner tree problem in Kalmanson matrices and in circulant matrices

B. Klinz, G.J. Woeginger

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    6 Citaten (Scopus)

    Samenvatting

    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.
    Originele taal-2Engels
    Pagina's (van-tot)51-58
    Aantal pagina's8
    TijdschriftJournal of Combinatorial Optimization
    Volume3
    Nummer van het tijdschrift1
    DOI's
    StatusGepubliceerd - 1999

    Vingerafdruk

    Duik in de onderzoeksthema's van 'The Steiner tree problem in Kalmanson matrices and in circulant matrices'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit