Article ID Journal Published Year Pages File Type
5128430 Operations Research Letters 2017 4 Pages PDF
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
, ,