This paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider different objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunication network design, but it can be useful in other fields. We achieve a complete characterization of its computational complexity, previously studied only for special cases: a polynomial algorithm based on a new matroid solves the easy cases; the others are strongly NP-hard by direct reduction from SAT. Finally, we give results on special graphs.

On the complexity of graph tree partition problems / R. Cordone, F. Maffioli. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - 134:1-3(2004 Jan), pp. 51-65.

On the complexity of graph tree partition problems

R. Cordone
Primo
;
2004

Abstract

This paper concerns the optimal partition of a graph into p connected clusters of vertices, with various constraints on their topology and weight. We consider different objectives, depending on the cost of the trees spanning the clusters. This rich family of problems mainly applies to telecommunication network design, but it can be useful in other fields. We achieve a complete characterization of its computational complexity, previously studied only for special cases: a polynomial algorithm based on a new matroid solves the easy cases; the others are strongly NP-hard by direct reduction from SAT. Finally, we give results on special graphs.
computational complexity; greedy algorithm; tree partition
Settore INF/01 - Informatica
gen-2004
Article (author)
File in questo prodotto:
Non ci sono file associati a questo prodotto.
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: https://hdl.handle.net/2434/6359
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 19
social impact