Approximating bounded-degree spanning trees and connected factors with leaves

Walter Kern; Bodo Manthey

doi:10.1016/j.orl.2017.01.002

Approximating bounded-degree spanning trees and connected factors with leaves

Walter Kern, Bodo Manthey

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

314 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 language	English
Pages (from-to)	115-118
Number of pages	4
Journal	Operations research letters
Volume	45
Issue number	2
DOIs	https://doi.org/10.1016/j.orl.2017.01.002
Publication status	Published - Mar 2017
Event	14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016) - University of Milan, Gargnano, Italy Duration: 6 Jun 2016 → 8 Jun 2016

Keywords

EWI-27055
IR-103354
Graph factors
Approximation algorithms

Access to Document

10.1016/j.orl.2017.01.002

Kern2017ConnectedAccepted author version, 242 KBLicence: CC BY-NC-ND

Cite this

@article{0518192bc5214eb5a67cea0d08a14aa0,

title = "Approximating bounded-degree spanning trees and connected factors with leaves",

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$.",

keywords = "EWI-27055, IR-103354, Graph factors, Approximation algorithms",

author = "Walter Kern and Bodo Manthey",

year = "2017",

month = mar,

doi = "10.1016/j.orl.2017.01.002",

language = "English",

volume = "45",

pages = "115--118",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "2",

note = "14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016), CTW 2016 ; Conference date: 06-06-2016 Through 08-06-2016",

}

TY - JOUR

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

AU - Kern, Walter

AU - Manthey, Bodo

PY - 2017/3

Y1 - 2017/3

N2 - 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$.

AB - 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$.

KW - EWI-27055

KW - IR-103354

KW - Graph factors

KW - Approximation algorithms

U2 - 10.1016/j.orl.2017.01.002

DO - 10.1016/j.orl.2017.01.002

M3 - Article

SN - 0167-6377

VL - 45

SP - 115

EP - 118

JO - Operations research letters

JF - Operations research letters

IS - 2

T2 - 14th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2016)

Y2 - 6 June 2016 through 8 June 2016

ER -

Approximating bounded-degree spanning trees and connected factors with leaves

Abstract

Keywords

Access to Document

Fingerprint

Cite this