2010 | OriginalPaper | Chapter
The (K,k)-Capacitated Spanning Tree Problem
Authors : Esther M. Arkin, Nili Guttmann-Beck, Refael Hassin
Published in: Algorithmic Aspects in Information and Management
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.