Partitioning a graph into connected components with fixed centers and optimizing cost‐based objective functions or equipartition criteria. Issue 1 (16th October 2015)

• Record Type: Journal Article
• Authors: Lari, Isabella; Ricca, Federica; Puerto, Justo; Scozzari, Andrea
• Is Part Of: Networks. Volume 67:Issue 1(2016)
• Page Start: 69
• Page End: 81
• Publication Date: 2015-10-16
• Subjects: p‐centered partitions -- tree partitioning -- flat costs -- min‐sum criterion -- min‐max criterion -- range criterion -- uniform partitions -- exactly uniform 2‐centered partition -- capacitated partitions; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21661
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : We consider a connected graph G with n vertices, p of which are centers, while the remaining ones are units . For each unit‐center pair, there is a fixed assignment cost and for each vertex there is a nonnegative weight. In this article, we study the problem of partitioning G into p connected components such that each component contains exactly one center ( p‐centered partition ). We analyze different optimization problems of this type by defining different objective functions based on the assignment costs, or on the vertices' weights, or on both of them. For these problems, we show that they are NP‐hard on very special classes of graphs, and for some of them we provide polynomial time algorithms when G is a tree. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(1), 69–81 2016