{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:15Z","timestamp":1759638555735},"reference-count":10,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,8]]},"abstract":"<jats:p> Assume that a tree T has a number n<jats:sub>s<\/jats:sub> of \"supply vertices\" and all the other vertices are \"demand vertices.\" Each supply vertex is assigned a positive number called a supply, while each demand vertex is assigned a positive number called a demand. One wishes to partition T into exactly n<jats:sub>s<\/jats:sub> subtrees by deleting edges from T so that each subtree contains exactly one supply vertex whose supply is no less than the sum of demands of all demand vertices in the subtree. 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. The first is a linear-time algorithm for the partition problem. The second is a pseudo-polynomial-time algorithm for the maximum partition problem. The third is a fully polynomial-time approximation scheme (FPTAS) for the maximum partition problem. <\/jats:p>","DOI":"10.1142\/s0129054105003303","type":"journal-article","created":{"date-parts":[[2005,7,5]],"date-time":"2005-07-05T14:52:13Z","timestamp":1120575133000},"page":"803-827","source":"Crossref","is-referenced-by-count":23,"title":["PARTITIONING TREES OF SUPPLY AND DEMAND"],"prefix":"10.1142","volume":"16","author":[{"given":"TAKEHIRO","family":"ITO","sequence":"first","affiliation":[{"name":"Graduate School of Information Sciences, Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japan"}]},{"given":"XIAO","family":"ZHOU","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences,  Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japan"}]},{"given":"TAKAO","family":"NISHIZEKI","sequence":"additional","affiliation":[{"name":"Graduate School of Information Sciences,  Tohoku University, Aoba-yama 6-6-05, Sendai, 980-8579, Japan"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1109\/61.974213"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90008-3"},{"key":"rf4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"rf7","volume-title":"Algorithms and Theory of Computation Handbook","author":"Klein P. N.","year":"1999"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/61.871365"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00083-5"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(98)00120-9"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322236"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1109\/61.974215"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:38:53Z","timestamp":1565138333000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":10,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,8]]}},"alternative-id":["10.1142\/S0129054105003303"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003303","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}