Approximating bounded-degree spanning trees and connected factors with leaves

Walter Kern, Bodo Manthey

Research output: Contribution to journalArticleAcademicpeer-review

201 Downloads (Pure)

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 languageEnglish
Pages (from-to)115-118
Number of pages4
JournalOperations research letters
Volume45
Issue number2
DOIs
Publication statusPublished - Mar 2017
Event14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016) - University of Milan, Gargnano, Italy
Duration: 6 Jun 20168 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.

Cite this