Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5128430 | Operations Research Letters | 2017 | 4 Pages |
Abstract
We present constant factor approximation algorithms for the following two problems: First, given a connected graph G=(V,E) with non-negative edge weights, find a minimum weight spanning tree that respects prescribed upper bounds on the vertex degrees. Second, given prescribed (exact) vertex degrees d=(di)iâV, find a minimum weight connected d-factor. Constant factor approximation algorithms for these problems were known only for the case that diâ¥2 for all iâV.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Walter Kern, Bodo Manthey,