ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    The Steiner Tree Problem in Kalmanson Matrices and in Circulant Matrices (1999)
    Springer
    Journal of combinatorial optimization 3 (1999), S. 51-58 
    Details
    ISSN: 1573-2886
    Keywords: Steiner tree ; Kalmanson matrix ; circulant matrix ; computational complexity ; graph algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: 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 $$\mathcal{N}\mathcal{P}$$ -hardness proof and thus establish computational intractability.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009881510868
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...