𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the complexity of graph tree partition problems

✍ Scribed by Roberto Cordone; Francesco Maffioli

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
270 KB
Volume
134
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

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 di erent 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 ΓΏelds. 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.

πŸ“œ SIMILAR VOLUMES

On tree-partitions of graphs
On tree-partitions of graphs
✍ Guoli Ding; Bogdan Oporowski πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 725 KB

A graph G admits a tree-partition of width k if its vertex set can be partitioned into sets of size at most k so that the graph obtained by identifying the vertices in each set of the partition, and then deleting loops and parallel edges, is a forest. In the paper, we characterize the classes of gra

On partitions of graphs into trees
On partitions of graphs into trees
✍ F.R.K. Chung πŸ“‚ Article πŸ“… 1978 πŸ› Elsevier Science 🌐 English βš– 934 KB

We crgnsider the minimum m\*-nber T(G) of subsets intl:, which the edge set E(G) of a graph G can lx partitioned so that each subset forms a tree. It is shown that for any connected (3 with II vertices, we always have T( Gj s [$I.