
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Partitioning Trees with Supply, Demand and EdgeCapacity
Masaki KAWABATA Takao NISHIZEKI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E96A
No.6
pp.10361043 Publication Date: 2013/06/01
Online ISSN: 17451337 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: tree, maximum partition problem, supply, demand, edgecapacity, approximation algorithm,
Full Text: PDF(1.2MB) >>Buy this Article
Summary:
Let T be a given tree. Each vertex of T is either a supply vertex or a demand vertex, and is assigned a positive number, called the supply or demand. Each demand vertex v must be supplied an amount of “power,” equal to the demand of v, from exactly one supply vertex through edges in T. Each edge is assigned a positive number called the capacity. One wishes to partition T into subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of all demands in the subtree and the power flow through each edge is no more than capacity of the edge. The “partition problem” is a decision problem to ask whether T has such a partition. The “maximum partition problem” is an optimization version of the partition problem. In this paper, we give three algorithms for the problems. First is a lineartime algorithm for the partition problem. Second is a pseudopolynomialtime algorithm for the maximum partition problem. Third is a fully polynomialtime approximation scheme (FPTAS) for the maximum partition problem.

