{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:11:38Z","timestamp":1761621098813},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2012,3]]},"abstract":"<jats:p> We study how to partition an interval graph with non-negative vertex weights into k connected subgraphs such that the minimum total weight of any part of the partition is maximized. For k = 2, it is shown that for any \u03b5 &gt; 0, a (1 + \u03b5)-approximation can be found in O((1\/\u03b5)n<jats:sup>3<\/jats:sup>) time, i.e., it admits a fully polynomial-time approximation scheme (FPTAS). For any fixed k &gt; 2, the problem also admits an FPTAS when restricted to k-connected interval graphs. <\/jats:p>","DOI":"10.1142\/s179383091250005x","type":"journal-article","created":{"date-parts":[[2012,4,9]],"date-time":"2012-04-09T21:24:02Z","timestamp":1334006642000},"page":"1250005","source":"Crossref","is-referenced-by-count":16,"title":["FULLY POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR THE MAX\u2013MIN CONNECTED PARTITION PROBLEM ON INTERVAL GRAPHS"],"prefix":"10.1142","volume":"04","author":[{"given":"BANG YE","family":"WU","sequence":"first","affiliation":[{"name":"Department of Computer Science and Information Engineering, National Chung Cheng University, ChiaYi 621, Taiwan, R.O.C."}]}],"member":"219","published-online":{"date-parts":[[2012,4,13]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199809)32:2<115::AID-NET4>3.0.CO;2-E"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-001-0008-8"},{"key":"rf3","first-page":"177","volume":"9","author":"Chataigner F.","journal-title":"Discrete Math. Theoret. Comput. Sci."},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00175-5"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90008-3"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00265-4"},{"key":"rf7","volume-title":"Computers and Intractability: A Guide to The Theory of NP-Completeness","author":"Garey M. R.","year":"1979"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1007\/BF01896190"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00083-5"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322236"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90189-5"},{"key":"rf12","first-page":"584","volume":"31","author":"Suzuki H.","journal-title":"J. Inform. Process. Soc. Japan"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383091250005X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T13:53:38Z","timestamp":1565186018000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383091250005X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2012,4,13]]},"published-print":{"date-parts":[[2012,3]]}},"alternative-id":["10.1142\/S179383091250005X"],"URL":"https:\/\/doi.org\/10.1142\/s179383091250005x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3]]}}}