Graph partitioning is a widely studied problem in the literature with several applications in real life contexts. In this paper we study the problem of partitioning a graph, with weights at its vertices, into p connected components. For each component of the partition we measure the difference between the maximum and the minimum weight of a vertex in the component. We consider two objective functions to minimize, one measuring the maximum of such differences among all the components in the partition, and the other measuring the sum of the differences between the maximum and the minimum weight of a vertex in each component. We focus our analysis on tree graphs and provide polynomial time algorithms for solving these optimization problems on such graphs. In particular, we present an O(n2logn) time algorithm for the min–max version of the problem on general trees and several, more efficient polynomial algorithms for some trees with a special structure, such as spiders and caterpillars. Finally, we present NP-hardness and approximation results on general graphs for both the objective functions.
On finding connected balanced partitions of trees / M. Bruglieri, R. Cordone, I. Lari, F. Ricca, A. Scozzari. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 299(2021 Aug), pp. 1-16.
|Titolo:||On finding connected balanced partitions of trees|
|Parole Chiave:||Connected partitioning of trees; Min-sum gap optimization; Min–max gap optimization|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||ago-2021|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.dam.2021.04.002|
|Appare nelle tipologie:||01 - Articolo su periodico|
File in questo prodotto:
|Ricca et al - Connected Balanced Tree Paritioning_REV1.pdf||Articolo||Pre-print (manoscritto inviato all'editore)||Open Access Visualizza/Apri|
|1-s2.0-S0166218X21001451-main.pdf||Publisher's version/PDF||Administrator Richiedi una copia|