| Title: | MINIMIZING CAPACITATED TREE COVERS OF GRAPHS
This research was partially supported by a Scientific Grant in Aid from the Ministry of Education, Culture, Sports, Science and Technology of Japan. |
| DOI No: | 10.1142/9781860948534_0012 |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 78-82)
|
| Author(s): | YOSHIYUKI KARUNO
Kyoto Institute of Technology, Sakyo, Kyoto 606-8585, Japan
HIROSHI NAGAMOCHI
Kyoto University, Sakyo, Kyoto 606-8501, Japan
|
| Abstract: | Let G = (V, E) be a simple connected graph such that each vertex ν ∈V and each edge e ∈ E are weighted by non-negative reals h(ν) and w(e), respectively. The capacitated subtree cover problem asks to find a partition  of V and a set  of subtrees such that each Ti contains Xi so that the cost of each Ti does not exceed a specified capacity d (> 0), where the cost of each Ti is defined by the sum of weights of edges in Ti and weights of vertices in Xi. The objective is to minimize the number  of subtrees. In this paper, we propose a constant factor approximation algorithm to the problem. |
| Full Text: | View full text in PDF format (251KB) |
| TOC: | Back to Table of Contents |
|
|
