Paper Info
Title
On the complexity of graph tree partition problems
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.
Year
DOI
Venue
2004
10.1016/S0166-218X(03)00340-8
Discrete Applied Mathematics
Keywords
Field
DocType
optimal partition,computational complexity,special case,different objective,easy case,complete characterization,new matroid,graph tree partition problem,direct reduction,p connected cluster,special graph,greedy algorithm,tree partition,topology,constraint,graph,complete,design,spanning tree,polynomial,cout,telecommunication network,weight,partition,problem,connected graph,reduction,tree graph,conception,matroid,graph theory,algorithm
Pseudoforest,Matroid,Graph theory,Discrete mathematics,Combinatorics,Tree (graph theory),Frequency partition of a graph,Spanning tree,Graph partition,Connectivity,Mathematics
Journal
Volume
Issue
ISSN
134
1-3
Discrete Applied Mathematics
Citations 
PageRank 
References 
13
0.88
6
Authors
2
Name
Order
Citations
PageRank
Roberto Cordone131028.87
Francesco Maffioli227144.39