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.
Partitioning a Graph into Connected Components with Fixed Centers and Optimizing Cost-Based Objective Functions or Equipartition Criteria / Lari, Isabella; Puerto, Justo; Ricca, Federica; Scozzari, Andrea. - In: NETWORKS. - ISSN 0028-3045. - 67:(2016), pp. 69-81. [10.1002/net]
Partitioning a Graph into Connected Components with Fixed Centers and Optimizing Cost-Based Objective Functions or Equipartition Criteria
LARI, Isabella;RICCA, Federica;
2016
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.File | Dimensione | Formato | |
---|---|---|---|
Ricca_Networks_2016.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
1.68 MB
Formato
Adobe PDF
|
1.68 MB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.