Approximating bounded-degree spanning trees and connected factors with leaves

作者：Kern Walter; Manthey Bodo^*

来源：Operations Research Letters, 2017, 45(2): 115-118.

DOI：10.1016/j.orl.2017.01.002

• Approximation algorithms
• Bounded-degree spanning trees
• Connected graph factors
• Network design

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 = (d(i))(i is an element of 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 is an element of V.

• 出版日期2017-3