The vertex degrees of minimum spanning trees

The vertex degrees of minimum spanning trees

0.00 Avg rating—0 Votes
Article ID: iaor20011468
Country: Netherlands
Volume: 125
Issue: 2
Start Page Number: 278
End Page Number: 282
Publication Date: Sep 2000
Journal: European Journal of Operational Research
Authors:
Keywords: Minimum spanning trees
Abstract:

We study the problem of minimum spanning trees (MST) with degree constraints. It is well known that this problem in general is NP-hard. It will be shown that in finite-dimensional Banach spaces there is a number such that a bounded degree MST can be computed as efficiently as an ordinary MST if the degree constraint is greater than this number.

Reviews

Required fields are marked *. Your email address will not be published.