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. [10.1016/j.dam.2021.04.002]

On finding connected balanced partitions of trees

R. Cordone;
2021-08

Abstract

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.
Connected partitioning of trees; Min-sum gap optimization; Min–max gap optimization
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
Article (author)
File in questo prodotto:
File Dimensione Formato  
Ricca et al - Connected Balanced Tree Paritioning_REV1.pdf

accesso aperto

Descrizione: Articolo
Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 847.56 kB
Formato Adobe PDF
847.56 kB Adobe PDF Visualizza/Apri
1-s2.0-S0166218X21001451-main.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.35 MB
Formato Adobe PDF
1.35 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

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: http://hdl.handle.net/2434/849661
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact