A ‘maximum node clustering’ problem

A ‘maximum node clustering’ problem

0.00 Avg rating0 Votes
Article ID: iaor2007363
Country: Netherlands
Volume: 11
Issue: 4
Start Page Number: 373
End Page Number: 385
Publication Date: Jun 2006
Journal: Journal of Combinatorial Optimization
Authors: , , ,
Keywords: graphs
Abstract:

In this note we introduce a graph problem, called Maximum Node Clustering (MNC). We prove that the problem (which is easily shown to be strongly NP-complete) can be approximated in polynomial time within a ratio arbitrarily close to 2. For the special case where the graph is a tree, the problem is NP-complete in the ordinary sense; for this case we present a pseudopolynomial algorithm based on dynamic programming, and a related Fully Polynomial Time Approximation Scheme (FPTAS). Also, the tree case is shown to be exactly solvable in O(2(2/3)npoly(n)) time, where n is the number of nodes.

Reviews

Required fields are marked *. Your email address will not be published.