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

Stony Brook University

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

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{6031705aa3b344549283813047d4ca7e,

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

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