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: | Croce Federico Della, Locatelli Marco, Grosso Andrea, Carello Giuliana |
Keywords: | graphs |
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