This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit-center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP-hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time.

Polynomial Algorithms for Partitioning a Tree into Single-Center Subtrees to Minimize Flat Service Costs / Apollonio, N.; Lari, Isabella; Puerto, J.; Ricca, Federica; Simeone, Bruno. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 51:(2008), pp. 78-89. [10.1002/net.20197]

Polynomial Algorithms for Partitioning a Tree into Single-Center Subtrees to Minimize Flat Service Costs

N. Apollonio
;
LARI, Isabella;RICCA, Federica;SIMEONE, Bruno
2008

Abstract

This paper deals with the following graph partitioning problem. Consider a connected graph with n nodes, p of which are centers, while the remaining ones are units. For each unit-center pair there is a fixed service cost and the goal is to find a partition into connected components such that each component contains only one center and the total service cost is minimum. This problem is known to be NP-hard on general graphs, and here we show that it remains such even if the service cost is monotone and the graph is bipartite. However, in this paper we derive some polynomial time algorithms for trees. For this class of graphs we provide several reformulations of the problem as integer linear programs proving the integrality of the corresponding polyhedra. As a consequence, the tree partitioning problem can be solved in polynomial time either by linear programming or by suitable convex nondifferentiable optimization algorithms. Moreover, we develop a dynamic programming algorithm, whose recursion is based on sequences of minimum weight closure problems, which solves the problem on trees in O(np) time.
2008
Tree partitioning; generalized packing problem; −1; 0; 1-perfect matrices; maximum closure; dynamic programming; NP-Complete problems
01 Pubblicazione su rivista::01a Articolo in rivista
Polynomial Algorithms for Partitioning a Tree into Single-Center Subtrees to Minimize Flat Service Costs / Apollonio, N.; Lari, Isabella; Puerto, J.; Ricca, Federica; Simeone, Bruno. - In: NETWORKS. - ISSN 0028-3045. - STAMPA. - 51:(2008), pp. 78-89. [10.1002/net.20197]
File allegati a questo prodotto
File Dimensione Formato  
Ricca_Polynomial-Algorithms_2008.pdf

solo gestori archivio

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