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.
2016
p-centered partitions; tree partitioning; flat costs
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/846671
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 7
social impact