# Approximating bounded-degree spanning trees and connected factors with leaves

Walter Kern, Bodo Manthey

## 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=(d_i)_{i \in V}$, find a minimum weight connected $d$-factor. Constant factor approximation algorithms for these problems were known only for the case that $d_i \geq 2$ for all $i \in V$.
Original language English 115-118 4 Operations research letters 45 2 https://doi.org/10.1016/j.orl.2017.01.002 Published - Mar 2017 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016) - University of Milan, Gargnano, ItalyDuration: 6 Jun 2016 → 8 Jun 2016

## Keywords

• EWI-27055
• IR-103354
• Graph factors
• Approximation algorithms

## Fingerprint

Dive into the research topics of 'Approximating bounded-degree spanning trees and connected factors with leaves'. Together they form a unique fingerprint.