Premium
Partitioning a graph into connected components with fixed centers and optimizing cost‐based objective functions or equipartition criteria
Author(s) -
Lari Isabella,
Ricca Federica,
Puerto Justo,
Scozzari Andrea
Publication year - 2016
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21661
Subject(s) - combinatorics , equipartition theorem , connected component , partition (number theory) , mathematics , vertex (graph theory) , graph , graph partition , vertex connectivity , connectivity , computer science , discrete mathematics , mathematical optimization , physics , quantum mechanics , magnetic field
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