The (K, k) -capacitated spanning tree problem

Esther M. Arkin; Nili Guttmann-Beck; Refael Hassin

doi:10.1016/j.disopt.2012.08.002

The (K, k) -capacitated spanning tree problem

Esther M. Arkin
, Nili Guttmann-Beck
, Refael Hassin

Applied Mathematics and Statistics

Academic College of Tel-Aviv - Yaffo
Tel Aviv University

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

3 Scopus citations

Abstract

This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K, and the others have capacity k < K. We prove that the problem can be approximated within a constant factor, and present better approximations when k is 1 or 2.

Original language	English
Pages (from-to)	258-266
Number of pages	9
Journal	Discrete Optimization
Volume	9
Issue number	4
DOIs	https://doi.org/10.1016/j.disopt.2012.08.002
State	Published - Nov 2012

Keywords

Approximation algorithms
Minimum capacitated spanning tree

Access to Document

10.1016/j.disopt.2012.08.002

Cite this

@article{56fb9e1de6da4a15a44f761b823ac2a6,

title = "The (K, k) -capacitated spanning tree problem",

abstract = "This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K, and the others have capacity k < K. We prove that the problem can be approximated within a constant factor, and present better approximations when k is 1 or 2.",

keywords = "Approximation algorithms, Minimum capacitated spanning tree",

author = "Arkin, \{Esther M.\} and Nili Guttmann-Beck and Refael Hassin",

year = "2012",

month = nov,

doi = "10.1016/j.disopt.2012.08.002",

language = "English",

volume = "9",

pages = "258--266",

journal = "Discrete Optimization",

issn = "1572-5286",

number = "4",

}

TY - JOUR

T1 - The (K, k) -capacitated spanning tree problem

AU - Arkin, Esther M.

AU - Guttmann-Beck, Nili

AU - Hassin, Refael

PY - 2012/11

Y1 - 2012/11

N2 - This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K, and the others have capacity k < K. We prove that the problem can be approximated within a constant factor, and present better approximations when k is 1 or 2.

AB - This paper considers a generalization of the capacitated spanning tree problem, in which some of the vertices have capacity K, and the others have capacity k < K. We prove that the problem can be approximated within a constant factor, and present better approximations when k is 1 or 2.

KW - Approximation algorithms

KW - Minimum capacitated spanning tree

UR - https://www.scopus.com/pages/publications/84866413022

U2 - 10.1016/j.disopt.2012.08.002

DO - 10.1016/j.disopt.2012.08.002

M3 - Article

AN - SCOPUS:84866413022

SN - 1572-5286

VL - 9

SP - 258

EP - 266

JO - Discrete Optimization

JF - Discrete Optimization

IS - 4

ER -

The (K, k) -capacitated spanning tree problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this