TY - JOUR

T1 - The geometric generalized minimum spanning tree problem with grid clustering

AU - Feremans, Corinne

AU - Grigoriev, Alexander

AU - Sitters, René

PY - 2006

Y1 - 2006

N2 - This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly NP-hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering.

AB - This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly NP-hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering.

KW - Approximations

KW - Complexity

KW - Generalized minimum spanning tree

KW - Grid clustering

UR - http://www.scopus.com/inward/record.url?scp=33845336865&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845336865&partnerID=8YFLogxK

U2 - 10.1007/s10288-006-0012-6

DO - 10.1007/s10288-006-0012-6

M3 - Article

AN - SCOPUS:33845336865

SN - 1619-4500

VL - 4

SP - 319

EP - 329

JO - 4OR

JF - 4OR

IS - 4

ER -