The (K, k)-capacitated spanning tree problem

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

doi:10.1007/978-3-642-14355-7_4

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: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

This paper considers a generalization of the capacitated spanning tree, in which some of the nodes 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
Title of host publication	Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings
Pages	25-34
Number of pages	10
DOIs	https://doi.org/10.1007/978-3-642-14355-7_4
State	Published - 2010
Event	6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010 - Weihai, China Duration: Jul 19 2010 → Jul 21 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6124 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010
Country/Territory	China
City	Weihai
Period	07/19/10 → 07/21/10

Access to Document

10.1007/978-3-642-14355-7_4

Cite this

Arkin, E. M., Guttmann-Beck, N., & Hassin, R. (2010). The (K, k)-capacitated spanning tree problem. In Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings (pp. 25-34). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6124 LNCS). https://doi.org/10.1007/978-3-642-14355-7_4

@inproceedings{939f0b8e6b5443f3a0814c5af837fcf0,

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

abstract = "This paper considers a generalization of the capacitated spanning tree, in which some of the nodes 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.",

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

year = "2010",

doi = "10.1007/978-3-642-14355-7\_4",

language = "English",

isbn = "3642143547",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "25--34",

booktitle = "Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings",

note = "6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010 ; Conference date: 19-07-2010 Through 21-07-2010",

}

Arkin, EM, Guttmann-Beck, N & Hassin, R 2010, The (K, k)-capacitated spanning tree problem. in Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6124 LNCS, pp. 25-34, 6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010, Weihai, China, 07/19/10. https://doi.org/10.1007/978-3-642-14355-7_4

The (K, k)-capacitated spanning tree problem. / Arkin, Esther M.; Guttmann-Beck, Nili; Hassin, Refael.
Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings. 2010. p. 25-34 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6124 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Arkin, Esther M.

AU - Guttmann-Beck, Nili

AU - Hassin, Refael

PY - 2010

Y1 - 2010

N2 - This paper considers a generalization of the capacitated spanning tree, in which some of the nodes 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, in which some of the nodes 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.

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

U2 - 10.1007/978-3-642-14355-7_4

DO - 10.1007/978-3-642-14355-7_4

M3 - Conference contribution

AN - SCOPUS:79956330146

SN - 3642143547

SN - 9783642143540

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 34

BT - Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings

T2 - 6th International Conference on Algorithmic Aspects in Information and Management, AAIM 2010

Y2 - 19 July 2010 through 21 July 2010

ER -

Arkin EM, Guttmann-Beck N, Hassin R. The (K, k)-capacitated spanning tree problem. In Algorithmic Aspects in Information and Management - 6th International Conference, AAIM 2010, Proceedings. 2010. p. 25-34. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-14355-7_4

The (K, k)-capacitated spanning tree problem

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this