{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:56:00Z","timestamp":1725544560927},"reference-count":19,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2007,11,28]],"date-time":"2007-11-28T00:00:00Z","timestamp":1196208000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2008,1]]},"abstract":"Abstract<\/jats:title>This paper deals with the following graph partitioning problem. Consider a connected graph with n<\/jats:italic> nodes, p<\/jats:italic> of which are centers, while the remaining ones are units. For each unit\u2010center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP\u2010hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O<\/jats:italic>(n<\/jats:italic>p<\/jats:italic>) time. \u00a9 2007 Wiley Periodicals, Inc. NETWORKS, 2008<\/jats:p>","DOI":"10.1002\/net.20197","type":"journal-article","created":{"date-parts":[[2007,11,28]],"date-time":"2007-11-28T16:20:04Z","timestamp":1196266804000},"page":"78-89","source":"Crossref","is-referenced-by-count":13,"title":["Polynomial algorithms for partitioning a tree into single\u2010center subtrees to minimize flat service costs"],"prefix":"10.1002","volume":"51","author":[{"given":"N.","family":"Apollonio","sequence":"first","affiliation":[]},{"given":"I.","family":"Lari","sequence":"additional","affiliation":[]},{"given":"F.","family":"Ricca","sequence":"additional","affiliation":[]},{"given":"B.","family":"Simeone","sequence":"additional","affiliation":[]},{"given":"J.","family":"Puerto","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,11,28]]},"reference":[{"key":"e_1_2_1_2_2","unstructured":"N.Apollonio I.Lari J.Puerto F.Ricca B.Simeone \u201cPartitioning a tree into single\u2010center subtrees to minimize flat service costs\u201d Technical Report Universidad de Sevilla Dep. to de Estadist\u00edca e Investigaci\u00f3n Operativa (in preparation)."},{"key":"e_1_2_1_3_2","first-page":"161","article-title":"On approximating arbitrary metrics by tree metrics","author":"Bartal Y.","year":"1998","journal-title":"Proc of the 30th Ann Symp Foundation Comput Sci"},{"key":"e_1_2_1_4_2","first-page":"114","article-title":"Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k\u2010median","author":"Charikar M.","year":"1998","journal-title":"Proc 30th Ann Symp Foundation Comput Sci"},{"key":"e_1_2_1_5_2","unstructured":"R.Cordone A short note on graph tree partition problems with assignment or communication objective functions Internal Report DEI 2001.7 (2001) Politecnico di Milano."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717105"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623498342186"},{"key":"e_1_2_1_8_2","volume-title":"Computers and intractability","author":"Garey M. R.","year":"1999"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.16.8.B495"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1080\/1055678021000060829a"},{"key":"e_1_2_1_11_2","volume-title":"SIAM Monographs on Discrete Mathematics and Applications","author":"di Cortona Grilli","year":"1999"},{"key":"e_1_2_1_12_2","series-title":"Surveys in combinatorial optimization","first-page":"83","author":"Hammer P. L.","year":"1987"},{"key":"e_1_2_1_13_2","volume-title":"Convex analysis and minimization algorithms","author":"Hiriart\u2010Urruty J. B.","year":"1996"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0137040"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1080\/03610929508831512"},{"key":"e_1_2_1_17_2","first-page":"57","volume-title":"Atti Giornate di Lavoro AIRO, Urbino 1978","author":"Simeone B.","year":"1978"},{"key":"e_1_2_1_18_2","first-page":"349","volume-title":"Discrete location theory","author":"Tansel B. C.","year":"1990"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.34.2.250"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592216"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20197","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20197","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T02:33:27Z","timestamp":1694572407000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20197"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,28]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1002\/net.20197"],"URL":"https:\/\/doi.org\/10.1002\/net.20197","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,28]]}}}