This paper addresses centered and non centered equipartition tree problems into connected components (p-partitions). In the former case, each partition must contain exactly one special vertex called center, whereas in the latter, partitions are not required to fulfill this condition. Among the different equipartition problems considered in the literature, we focus on: (1) Most Uniform Partition (MUP) and (2) Uniform Partition (UP). Both criteria are defined either w.r.t. weights assigned to each vertex or to costs assigned to each vertex–center pair. Costs are assumed to be flat, i.e., they are independent of the topology of the tree. With respect to costs, MUP minimizes the difference between the maximum and minimum cost of the components of a partition and UP resorts to optimal min–max or max–min partitions. We provide polynomial time algorithms for centered and non centered versions of the MUP problem on trees when weights are assigned to each vertex. In the non centered case, our results set as polynomial the complexity of this problem which was an open question for several years. On the contrary, we prove that the centered version of MUP with flat costs is NP-complete even on trees. For the UP problem, we develop polynomial time algorithms for the max–min and min–max centered p-partition problems on trees both in the case of weight and cost-based objective functions.

Uniform and most uniform partitions of trees / Lari, Isabella; Puerto, Justo; Ricca, Federica; Scozzari, Andrea. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - 30:(2018), pp. 96-107. [10.1016/j.disopt.2018.06.003]

Uniform and most uniform partitions of trees

Isabella Lari;Federica Ricca;
2018

Abstract

This paper addresses centered and non centered equipartition tree problems into connected components (p-partitions). In the former case, each partition must contain exactly one special vertex called center, whereas in the latter, partitions are not required to fulfill this condition. Among the different equipartition problems considered in the literature, we focus on: (1) Most Uniform Partition (MUP) and (2) Uniform Partition (UP). Both criteria are defined either w.r.t. weights assigned to each vertex or to costs assigned to each vertex–center pair. Costs are assumed to be flat, i.e., they are independent of the topology of the tree. With respect to costs, MUP minimizes the difference between the maximum and minimum cost of the components of a partition and UP resorts to optimal min–max or max–min partitions. We provide polynomial time algorithms for centered and non centered versions of the MUP problem on trees when weights are assigned to each vertex. In the non centered case, our results set as polynomial the complexity of this problem which was an open question for several years. On the contrary, we prove that the centered version of MUP with flat costs is NP-complete even on trees. For the UP problem, we develop polynomial time algorithms for the max–min and min–max centered p-partition problems on trees both in the case of weight and cost-based objective functions.
2018
Graph partitioning; Most uniform partition problems; Centered partitions; Equipartition problems
01 Pubblicazione su rivista::01a Articolo in rivista
Uniform and most uniform partitions of trees / Lari, Isabella; Puerto, Justo; Ricca, Federica; Scozzari, Andrea. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - 30:(2018), pp. 96-107. [10.1016/j.disopt.2018.06.003]
File allegati a questo prodotto
File Dimensione Formato  
Ricca_Uniform_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 760.24 kB
Formato Adobe PDF
760.24 kB 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/1173809
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact